A lower bound for the irredundance number of trees

• Autorzy: Michael Poschen , Lutz Volkmann
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

irredundance; tree; domination

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2006
• Tom: 26
• Numer: 2
• Strony: 209-215

Daty

wydano

2006

otrzymano

2005-05-20

poprawiono

2006-02-23

Twórcy

autor

Michael Poschen

• Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany

autor

Lutz Volkmann

• Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1313