Hamiltonian Properties On Claw-Free Graphs And Generalizations Of Claw-Free Graphs

It is well known that it is a NP-completeness to judge a general graph if it has hamiltonian properties. Though claw-free graphs have already been restricted on general graphs, it is also a NP-completeness to judge a claw-free graph if it has hamiltonian properties. Therefore, many scholars do a lot of research on some special claw-free graphs and obtain many conclusions on Hamiltonian properties of claw-free graphs. The research of my dissertation was motivated by Matthews and Sumner’s conjecture that every4-connected claw-free graph is hamiltonian. We discuss the hamiltonian properties of quadrangularly connected claw-free graphs,{(P6)2, hour-glass, claw}-free graphs, quasilocally2-connected claw-free graphs, almost locally connected claw-free graphs, respectively. We also give the range of the circumference of2-connected not in (?)1quasi-claw-free graphs, which is a generalization of claw-free graphs.This dissertation contains the main research results as follows,(1) Li, Guo, Xiong et al. propose the conjecture that if G is a connected quadrangularly connected claw-free graphs with δ(G)≥3and does not contain a subgraph H isomorphic to H1or H2, in which the vertices with degree4are not locally connected, then G is vertex pancyclic. We give a counterexample to the conjecture, and increase the lower bound of δ(G) in the conditions of the conjecture to5, then the conclusion of the above conjecture is true. Since quadrangularly connected graphs contain locally connected graphs,N2-locally connected graphs and triangularly connected graphs, in a way, the result about vertex pancyclicity of quadrangularly connected claw-free graphs develops the conclusion of vertex pancyclicity of the above special claw-free graphs.(2) In this dissertation, we prove the Hamilton-connectedness of4-connected{(P6)2, hour-glass, claw}-free graphs. This conclusion gets closer to verify the conjecture by Matthews and Sumner that every4-connected claw-free graph is hamiltonian. On the basic of the definition of quasilocally connected graph, we give the definition of quasilocally n-connected graphs. Obviously quasilocally2-connected graphs contain locally2-connected graphs. Kanetkar and Rao prove that every connected locally2-connected claw-free graph is panconnected. We give an example of a quasilocally2-connected claw-free graph which is not panconnected, and prove that every connected quasilocally2-connected claw-free graph is Hamilton-connected. This conclusion, to some extent, generalizes Kanetkar and Rao’s result. Asratian proposes that every locally connected claw-free graph G is Hamilton-connected if and only if G is3-connected. We prove that every almost locally connected claw-free graph G is Hamilton-connected if and only if G is3-connected, which generalizes the above Asratian’s conclusion.(3) Quasi-claw-free graph is a generalization of claw-free graphs. Li proves that if G is a2-connected claw-free graph with order n and G (?)1, then G contains a cycle of length at least min{3δ+2, n}. We prove that if a2-connected quasi-claw-free graph G(?)with order n, then G contains a cycle of length at least min{3δ+2, n). This conclusion confirms that quasi-claw-free graphs, which is a generalization of claw-free graphs, have similar properties of hamilton and circumference to claw-free graphs.