Research Of Existing Sufficient Conditions Of Tutte Trees With K-trees And Relationship In Graphs

Let G be a connected graph.A spanning tree of a graph is a Tutte tree if every path in the tree is nonseparating;a k-tree of a graph is a tree with maximum degree at most k.We first consider that a graph G containing a Hamilton path has a Tutte tree when it satisfies certain conditions.Next7,we give sufficient conditions for a graph G to have spanning k-trees with specified vertices satisfying some conditions:(1)Let k and s be integers with k?3 and k?s suppose that G with |G|?2s+ 1 is(s+ 1)-connected and the degree sum of any k independent vertices is at least |G|+(2k-1)s-k,then for any s distinct vertices of G,G has a spanning k-tree such that the s specified vertices are contained in the set of leaves;(2)Let k.m,and n be integers with k?2,and n-k?m?1,suppose that G is n-connected and the independence number is at most m,then for any k distinct vertices of G,G has a spanning k-tree such that the k specified vertices are leaves;(3)Let k,s and n be integers with k?3 and n??1,suppose that G is n-connected and the independence number is at most n(k-1)-sk?1,then for any s distinct vertices of G,G has a spanning k-tree such that the each specified vertex has degree less than k;these results generalize theorem which guarantees the existence of a spanning k-tree such that any s distinct vertices are contained in the set of leaves.Then,we proof sufficient conditions for the existence of spanning k-trees using induction:let k be an integer with k?3 and let G be a graph of order n and the connectivity is at least 1,if for any l is at least connectivity of G,there exists an integer t such that 1?t?k-1)l +2-?l-1/k?and the degree sum of any k independent vertices is at least n+tl-kl-1,then G has a spanning k-tree.And we consider the relationship of Tutte trees and spanning 2-trees or spanning 3-trees.