Independence Numbers in Trees

Min-Jen Jou¹, Jenq-Jong Lin^2*

¹Department of Information Technology, Ling Tung University, Taichung City.
²Department of Finance, Ling Tung University, Taichung City.

DOI: 10.4236/ojdm.2015.53003                

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

Independent Set, Independence Number, Tree

Conflicts of Interest

The authors declare no conflicts of interest.

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