| It is well-known that determining whether a given graph has a Hamiltonpath or not is NP-complete. A spanning tree of a graph is a spanning subgraphwhich is a tree. A Hamilton path can be viewed as a spanning tree with onlytwo leaves. It is widely believed that it is impossible to find non-trivial necessaryand sufcient conditions for a given graph to have a spanning tree with specialproperties, which are generalization of the Hamilton path problem. A spanningspider of a graph G is a spanning tree T of G with at most one vertex havingdegree more than three in T. In a spanning spider, if all of its legs, except possiblyone, consist of a single edge, we call it a spanning comet. This thesis gives twodegree sum conditions for the existence of a spanning comet. Which answer aproblem posed by Flandrin et al..In Chapter1, we introduce some basic notations and terminologies aboutspanning trees. Then we give a brief overview of some important results and prob-lems about existence of spanning trees, which are generalizations of the Hamiltonpath problem, most of them focus on special properties of the spanning tress in-cluding the number of leaves, the maximum degree, and the number of branchingof the trees.In Chapters2, we present a degree sum condition for the existence of aspanning comet in a given graph and also give examples to show that the degreesum condition can not be improved.At last, in Chapter3, we prove another degree sum condition for the existenceof a spanning comet and give examples to show that the condition can not beimproved when the order of G is relative small. However the degree sum conditiondoes not seem to be best possible when the order of the graph is large enough.We propose a conjecture in which the bound on the degree sum would be tight ifthe conjecture is true. |
