Independence Trees and Hamilton Cycles

摘要

Let G be on a connected graph on n vertices. A spanning tree T of G is called anindependence tree if the set of end vertices of T (vertices with degree one T) in an independent set in G. If G has an independence tree, then alpha(sub t) (G) denotes the maximum number of end vertices of an independence tree of G. We show that determining alpha(sub t) of a graph is an NP-hard problem. We then provide and prove several theorems including Ore and Bondy Chvatal.