Lower bound on the domination number of a tree

• Autorzy: Magdalena Lemańska
• Języki publikacji: EN

Abstrakty

EN

>We prove that the domination number γ(T) of a tree T on n ≥ 3 vertices and with n₁ endvertices satisfies inequality γ(T) ≥ (n+2-n₁)/3 and we characterize the extremal graphs.

Słowa kluczowe

EN

domination number; tree

Kategorie tematyczne

• 05C05: Trees
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2004
• Tom: 24
• Numer: 2
• Strony: 165-169

Daty

wydano

2004

otrzymano

2001-09-24

poprawiono

2003-12-10

Twórcy

autor

Magdalena Lemańska

• Department of Mathematics, Gdańsk University of Technology, Narutowicza 11/12, 80-952 Gdańsk, Poland

Bibliografia

• [1] O. Favaron, A bound on the independent domination number of a tree, Vishwa International Journal of Graph Theory 1 (1992) 19-27.
• [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan. London, 1976).

Identyfikatory

DOI

10.7151/dmgt.1222