On domination and annihilation in graphs with claw-free blocks (Q5937584)
From MaRDI portal
scientific article; zbMATH DE number 1619835
Language | Label | Description | Also known as |
---|---|---|---|
English | On domination and annihilation in graphs with claw-free blocks |
scientific article; zbMATH DE number 1619835 |
Statements
On domination and annihilation in graphs with claw-free blocks (English)
0 references
28 November 2001
0 references
Let \(\gamma(G)\) and \(\text{ir}(G)\) be the domination and irredundance numbers of a graph \(G\). Extending \textit{P. Damaschke}'s result [Discrete Math. 89, No. 1, 101-104 (1991; Zbl 0753.05068)] for trees, \textit{L. Volkmann} [Discrete Math. 178, No. 1-3, 221-228 (1998; Zbl 0888.05037)] proved that \(\gamma(G)/ \text{ir}(G)\leq 3/2\) for any block graph. \textit{O. Favaron, V. Kabanov}, and \textit{J. Puech} [J. Comb. Math. Comb. Comput. 31, 151-159 (1999; Zbl 0944.05071)] obtained the same bound for every claw-free graph. Furthermore, \textit{V. E. Zverovich} [J. Graph Theory 29, No. 3, 139-149 (1998; Zbl 0919.05034)] showed that \(\gamma(G)/\text{ir}(G)<8/5\), when \(G\) is a block-catus graph, which was conjectured by Volkmann in the article mentioned above for cactus graphs. In this very nice paper, the authors prove \(\gamma(G)/\text{ir}(G)\leq 7/4\) for any graph whose blocks are claw-free. Examples show that this bound is best possible. Some related inequalities are also presented.
0 references
domination
0 references
irredundance
0 references
annihilation
0 references
block
0 references
claw
0 references