PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 209-215
DOI: https://doi.org/10.7151/dmgt.1313

A LOWER BOUND FOR THE IRREDUNDANCE NUMBER OF TREES

Michael Poschen and Lutz Volkmann

Lehrstuhl II für Mathematik
RWTH Aachen University
52056 Aachen, Germany
e-mail: volkm@math2.rwth-aachen.de

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−n1(T) 3  .

In this paper we prove

ir(T) ≥ n(T)+2−n1(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.

Keywords: irredundance, tree, domination.

2000 Mathematics Subject Classification: 05C69.

References

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

Received 20 May 2005
Revised 23 February 2006