Premium
The ratio of the irredundance number and the domination number for block‐cactus graphs
Author(s) -
Zverovich V. E.
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199811)29:3<139::aid-jgt2>3.0.co;2-r
Subject(s) - combinatorics , mathematics , cactus , conjecture , graph , discrete mathematics , graph power , line graph , botany , biology
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 Cockayne [ J. Graph Theory (1979) 241–249] proved independently that γ( G ) < 2 ir ( G ) for any graph G . For a tree T , Damaschke [ Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ( T ) < 3 ir ( T ). Extending Damaschke's result, Volkmann [ Discrete Math. (1998) 221–228] proved that 2γ( G ) ≤ 3 ir ( G ) for any block graph G and for any graph G with cyclomatic number μ( G ) ≤ 2. Volkmann also conjectured that 5γ( G ) < 8 ir ( 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 ) < 8 ir ( G ) for a block‐cactus graph G , thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998