PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | 26 | 2 | 209-215
Tytuł artykułu

A lower bound for the irredundance number of trees

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
26
Numer
2
Strony
209-215
Opis fizyczny
Daty
wydano
2006
otrzymano
2005-05-20
poprawiono
2006-02-23
Twórcy
  • Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1313
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.