Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of Lemańska's result.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1313,
author = {Michael Poschen and Lutz Volkmann},
title = {A lower bound for the irredundance number of trees},
journal = {Discussiones Mathematicae Graph Theory},
volume = {26},
year = {2006},
pages = {209-215},
zbl = {1142.05061},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1313}
}
Michael Poschen; Lutz Volkmann. A lower bound for the irredundance number of trees. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 209-215. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1313/
[000] [1] E.J. Cockayne, Irredundance, secure domination, and maximum degree in trees, unpublished manuscript (2004). | Zbl 1233.05143
[001] [2] E.J. Cockayne, P.H.P. Grobler, S.T. Hedetniemi and A.A. McRae, What makes an irredundant set maximal? J. Combin. Math. Combin. Comput. 25 (1997) 213-224. | Zbl 0907.05032
[002] [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). | Zbl 0890.05002
[003] [4] M. Lemańska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory 24 (2004) 165-169, doi: 10.7151/dmgt.1222. | Zbl 1063.05035