The Ratio of the Irredundance Number and the Domination Number for Block-Cactus Graphs

Zverovich, Vadim

Abstract

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) < 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. © 1998 John Wiley & Sons, Inc.

• Journal Article Type: Article
• Publication Date: Jan 1, 1998
• Deposit Date: Sep 24, 2015
• Publicly Available Date: Feb 19, 2016
• Journal: Journal of Graph Theory
• Print ISSN: 0364-9024
• Electronic ISSN: 1097-0118
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 29
• Issue: 3
• Pages: 139-149
• DOI: https://doi.org/10.1002/%28SICI%291097-0118%28199811%2929%3A3%3C139%3A%3AAID-JGT2%3E3.0.CO%3B2-R
• Keywords: graphs, domination number, irredundance number
• Public URL: https://uwe-repository.worktribe.com/output/1099260
• Publisher URL: http://dx.doi.org/10.1002/(SICI)1097-0118(199811)29:33.0.CO;2-R
• Additional Information: Additional Information : This is the peer reviewed version of the following article: Zverovich, V. (1998) The ratio of the irredundance number and the domination number for block-cactus graphs. Journal of Graph Theory, 29 (3). pp. 139-149. ISSN 0364-9024, which has been published in final form at http://dx.doi.org/10.1002/(SICI)1097-0118(199811)29:33.0.CO;2-R. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.
• Contract Date: Feb 19, 2016