Independence Numbers in Trees

Abstract

The independence number of a graph G is the maximum cardinality among all independent sets of G. For any tree T of order n ≥ 2, it is easy to see that . In addition, if there are duplicated leaves in a tree, then these duplicated leaves are all lying in every maximum independent set. In this paper, we will show that if T is a tree of order n ≥ 4 without duplicated leaves, then . Moreover, we constructively characterize the extremal trees T of order n ≥ 4, which are without duplicated leaves, achieving these upper bounds.

Keywords

Share and Cite:

Jou, M. and Lin, J. (2015) Independence Numbers in Trees. Open Journal of Discrete Mathematics, 5, 27-31. doi: 10.4236/ojdm.2015.53003.

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Application. North-Holland, New York. [2] Harant, J. (1998) A Lower Bound on the Independence Number of a Graph. Discrete Mathematics, 188, 239-243. http://dx.doi.org/10.1016/S0012-365X(98)00048-X [3] Hattingh, J.H., Jonack, E., Joubert, E.J. and Plummer, A.R. (2007) Total Restrained Domination in Trees. Discrete Mathematics, 307, 1643-1650. http://dx.doi.org/10.1016/j.disc.2006.09.014 [4] Jou, M.-J. (2010) Dominating Sets and Independent Sets in a Tree. Ars Combinatoria, 96, 499-504. [5] Jou, M.-J. (2010) Upper Domination Number and Domination Number in a Tree. Ars Combinatoria, 94, 245-250. [6] Luo, R. and Zhao, Y. (2006) A Note on Vizing’s Independence Number Conjecture of Edge Chromatic Critical Graphs, Discrete Mathematics, 306, 1788-1790. http://dx.doi.org/10.1016/j.disc.2006.03.040