Hamilton Connectedness And The Characterization Of Spanning Trees

The property of Hamiltonian in a graph has been an important and profound research topic in structural graph theory. The origin and development of the prob-lem, which have attracted the experts’ and scholars’ attention all over the world, are closely related to the Four Colour Conjecture in structural graph theory. The problem of hamiltonian paths is also closely related to the research of Hamiltonian in structural graph theory. According to the algorithm complexity, the problem of determining whether a given graph has a hamiltonian path or not is N P-complete. Therefore, the scholars mainly deal with sufficient conditions for a graph to have such a hamiltonian path.With respect to Hamilton connected, the known sufficient conditions mainly include two important types. The first one is based on the parameters such as in-dependence number, degree sum conditions, minimum degree, neighborhood union and so on. The second one is based on some specific forbidden subgraphs in struc-tural graph theory. Let H. be a family of connected graphs. A graph G is called H-free if G does not contain H as an induced subgraph for any H € H, and we call each H a forbidden subgraph. A graph G is called claw-free if it is K1,3-free. In the paper [J].R. Faudree, R. J. Faudree, Z. Ryjacek and P. Vrana, On forbidden pairs implying Hamiltion-connectedness, J Graph Theory 72 (2012),247-365.], Faudree et al. have shown that if G is a 3-connected{X, Y}-free graph for X= K1,3 and Y ∈{P8,N1,1,3,N1,2,2}) then G is Hamilton connected. In the second section, we improve their conclusions and show that every 3-connected{K1,3, N1,2,3}-free graph is Hamilton connected.Note that there is a hamiltonian path in a graph G if and only if G satisfies one of the following conditions:(i) G has a spanning tree with exactly 2 leaves.(ii) G has a spanning tree with no branch vertices.(iii) G has a spanning tree with maximum degree at most 2. Hence, the following problems are the natural extension of hamiltonian paths.(1) G has a spanning tree with at most k leaves.(2) G has a spanning tree with at most k branch vertices.(3) G has a spanning tree with maximum degree at most k.In the current study of three types of spanning trees above, the parameters we utilize mainly include independence number, toughness, degree sum conditions, minimum degree, neighborhood union and so on. In the paper [H. Matsuda, K. Ozeki and T. Yamashita, Spanning trees with a bounded number of branch vertices in a claw-free graph, Graphs and Combinatorics.30(2014) 429-437.], Matsuda, Ozeki and Yamashita have shown that let K be a non-negative integer. A connected claw-free graph G has a spanning tree with at most k branch vertices if α(G)≤2k+2. In the third section, we will prove that let k and r be two integers with k≥ 2 and γ> 4 and let G be a 2-connected K1,γ-free graph. If a(G)≤ k+ [(k+1)/r-3] - [1/|r-k-33|], then G has a spanning tree with at most k leaves and the upper bound of independence number is the best possible. Then, we get the following corollary that let k be an non-negative integer and let G be a 2-connected K1,4-free graph. If α(G)≤ 2k + 5, then G has a spanning tree with at most k branch vertices. Furthermore, we prove the following theorem that let k be an non-negative integer and let G be a connected K1,4-free graph. If a(G) ≤ 2k+5, then G has a spanning tree with at most k branch vertices or there exists a block B in G with α(B)< 2. At last, we pose the conjecture that a 2-connected claw-free graph G has a spanning tree with at most k leaves if α(G)≤ 2k + 2, where k is an integer with K≥ 2.