ArticleOriginal scientific text
Title
Lower bound on the domination number of a tree
Authors 1
Affiliations
- Department of Mathematics, Gdańsk University of Technology, Narutowicza 11/12, 80-952 Gdańsk, Poland
Abstract
>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.
Keywords
domination number, tree
Bibliography
- O. Favaron, A bound on the independent domination number of a tree, Vishwa International Journal of Graph Theory 1 (1992) 19-27.
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan. London, 1976).
Pages:
165-169
Main language of publication
English
Received
2001-09-24
Accepted
2003-12-10
Published
2004
DOI: 10.7151/dmgt.1222
Exact and natural sciences