Spanning k-ended trees of bipartite graphs
Review articleOpen access
Abstract:

AbstractA tree is called a k-ended tree if it has at most k leaves, where a leaf is a vertex of degree one. We prove the following theorem. Let k≥2 be an integer, and let G be a connected bipartite graph with bipartition (A,B) such that |A|≤|B|≤|A|+k−1. If σ2(G)≥(|G|−k+2)/2, then G has a spanning k-ended tree, where σ2(G) denotes the minimum degree sum of two non-adjacent vertices of G. Moreover, the condition on σ2(G) is sharp. It was shown by Las Vergnas, and Broersma and Tuinstra, independently that if a graph H satisfies σ2(H)≥|H|−k+1 then H has a spanning k-ended tree. Thus our theorem shows that the condition becomes much weaker if a graph is bipartite.

Request full text

References (0)

Cited By (0)

No reference data.
No citation data.
Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!