Independence Numbers in Trees - Open Journal of Discrete Mathematics

OJDM > Vol.5 No.3, July 2015

Independence Numbers in Trees ()

HTML XML

Download as PDF (Size: 292KB) PP. 27-31

DOI: 10.4236/ojdm.2015.53003 5,271 Downloads 7,157 Views Citations

Author(s)

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

Affiliation(s)

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

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

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.

Journals Menu

Follow SCIRP

	+1 323-425-8868
	customer@scirp.org
	+86 18163351462(WhatsApp)
	1655362766

	Paper Publishing WeChat

Journals Menu

Home

About SCIRP

Service

Policies