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 alpha(t)(G) denotes the maximum number of end vertices of an independence tree of G. We show that determining at of a graph is an NP-hard problem. We give the following analogue of a well-known result 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 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 Iless than or equal to 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-less than or equal to k-tree. Finally, we prove the following analogue of a closure theorem due to Bondy 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 if and only if G + uv has an I-less than or equal to k-tree (k 1 2). The last three results are all best possible with respect to the degree sum conditions. (C) 1998 John Wiley & Sons, Inc. J Graph Theory 29: 227-237, 1998. [References: 10]