INDEPENDENCE TREES AND HAMILTON CYCLES

Let G be a connected graph on n vertices. A spanning tree T of G is ca lled an independence tree, if the set of end vertices of T (vertices w ith degree one in T) is an independent set in G. If G has an independe nce tree, then alpha(t)(G) denotes the maximum number of end vertices of an independence tree of G. We show that determining at of a graph i s an NP-hard problem. We give the following analogue of a well-known r esult due to Chvatal and Erdos. If alpha(t)(G) less than or equal to ( k)(G) - 1, then G is hamiltonian. We show that the condition is sharp. An I-less than or equal to k-tree of G is an independence tree of G w ith at most k end vertices or a Hamilton cycle of G. We prove the foll owing two generalizations of a theorem of Ore. If G has an independenc e tree T with k end vertices such that two end vertices of T have degr ee sum at least n - k + 2 in G, then G has an Iless than or equal to k -1-tree. If the degree sum of each pair of nonadjacent vertices of G i s at least n - k + 1, then G has an I-less than or equal to k-tree. Fi nally, we prove the following analogue of a closure theorem due to Bon dy and Chvatal. If the degree sum of two nonadjacent vertices u and v of G is at least n - 1, then G has an I-less than or equal to k-tree i f and only if G + uv has an I-less than or equal to k-tree (k 1 2). Th e last three results are all best possible with respect to the degree sum conditions. (C) 1998 John Wiley & Sons, Inc. J Graph Theory 29: 22 7-237, 1998.