# A lower bound for the irredundance number of trees

Michael Poschen; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 2, page 209-215
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMichael Poschen, and Lutz Volkmann. "A lower bound for the irredundance number of trees." Discussiones Mathematicae Graph Theory 26.2 (2006): 209-215. <http://eudml.org/doc/270471>.

@article{MichaelPoschen2006,

abstract = {
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.
},

author = {Michael Poschen, Lutz Volkmann},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {irredundance; tree; domination},

language = {eng},

number = {2},

pages = {209-215},

title = {A lower bound for the irredundance number of trees},

url = {http://eudml.org/doc/270471},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Michael Poschen

AU - Lutz Volkmann

TI - A lower bound for the irredundance number of trees

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 2

SP - 209

EP - 215

AB -
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.

LA - eng

KW - irredundance; tree; domination

UR - http://eudml.org/doc/270471

ER -

## References

top- [1] E.J. Cockayne, Irredundance, secure domination, and maximum degree in trees, unpublished manuscript (2004). Zbl1233.05143
- [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. Zbl0907.05032
- [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
- [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. Zbl1063.05035

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.