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.
Cite this paper: Jou, M. and Lin, J. (2015) Independence Numbers in Trees. Open Journal of Discrete Mathematics, 5, 27-31. doi: 10.4236/ojdm.2015.53003.
References

[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

Top