×

The ratio of the irredundance number and domination number for block-cactus graphs. (English) Zbl 0919.05034

Summary: Let \(\gamma(G)\) and \(\text{ir}(G)\) denote the domination number and the irredundance number of a graph \(G\), respectively. R. B. Allan and R. Laskar [Proc. 9th Southeast Conf. on Combinatorics, Graph Theory and Computing, Boca Raton 1978, 43-56 (1978; Zbl 0404.05050)] and B. Bollobás and E. J. Cockayne [J. Graph Theory 3, 241-249 (1979; Zbl 0418.05049)] proved independently that \(\gamma(G)< 2\text{ir}(G)\) for any graph \(G\). For a tree \(T\), P. Damaschke [Discrete Math. 89, No. 1, 101-104 (1991; Zbl 0753.05068)] obtained the sharper estimation \(2\gamma(T)< 3\text{ir}(T)\). Extending Damaschke’s result, L. Volkmann [Discrete Math. 178, No. 1-3, 221-228 (1998; Zbl 0888.05037)] proved that \(2\gamma(G)\leq 3\text{ir}(G)\) for any block graph \(G\) and for any graph \(G\) with cyclomatic number \(\mu(G)\leq 2\). Volkmann also conjectured that \(5\gamma(G)< 8\text{ir}(G)\) for any cactus graph. In this article, we show that if \(G\) is a block-cactus graph having \(\pi(G)\) induced cycles of length \(2\pmod 4\), then \(\gamma(G)(5\pi(G)+ 4)\leq \text{ir}(G)(8\pi(G)+ 6)\). This result implies the inequality \(5\gamma(G)< 8\text{ir}(G)\) for a block-cactus graph \(G\), thus proving the above conjecture.

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI