DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 209-215
DOI: 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 n1(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