Independence trees and Hamilton cycles

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