Independence trees and Hamilton cycles
Hajo J. Broersma, Hilde Tuinstra · Journal of Graph Theory · 1998
Let G be a connected graph on n vertices. A spanning tree T of G is called an independence tree, if the set of end vertices of T (vertices with degree one in T) is an independent set in G. If G has an independence tree, then αt(G) denotes the maximum number of end vertices of an independence tree of G. We show that determining αt of a graph is an NP-hard problem. We give the following analogue of a well-known result due to Chvátal and Erdös. If αt(G) ≤ κ(G) − 1, then G is hamiltonian. We show that the condition is sharp. An I≤k-tree of G is an independence tree of G with at most k end vertices or a Hamilton cycle of G. We prove the following two generalizations of a theorem of Ore. If G has an independence tree T with k end vertices such that two end vertices of T have degree sum at least n − k + 2 in G, then G has an I≤k−1-tree. If the degree sum of each pair of nonadjacent vertices of G is at least n − k + 1, then G has an I≤k-tree. Finally, we prove the following analogue of a closure theorem due to Bondy and Chvátal. If the degree sum of two nonadjacent vertices u and v of G is at least n − 1, then G has an I≤k-tree if and only if G + uv has an I≤k-tree (k ≥ 2). The last three results are all best possible with respect to the degree sum conditions. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 227–237, 1998