The ratio of the irredundance number and the domination number for block-cactus graphs

✍ Scribed by Zverovich, V. E.

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 96 KB
• Volume: 29
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199811)29:3<139::aid-jgt2>3.0.co;2-r

✦ Synopsis

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43-56] and Bollobás and Cock- ayne [J. Graph Theory (1979) 241-249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T , Damaschke [Discrete Math. (1991) 101-104] obtained the sharper estimation 2γ(T ) < 3ir(T ). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221-228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number µ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture.