Independence Numbers in Trees


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.

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.
[3] Hattingh, J.H., Jonack, E., Joubert, E.J. and Plummer, A.R. (2007) Total Restrained Domination in Trees. Discrete Mathematics, 307, 1643-1650.
[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.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.