Hamiltonicity Of Quasi-claw-free Graphs

Hamilton properties have been a subject of many authors in the recent years.In 1857,the Ireland mathematician--Hamilton raised the problem:"If a connectedgraph is Hamiltonian, what is its complete and necessary conditions?"To thisday, it is not resolved and later it is found a NPC problem. So people studiedit in two ways: studying its complete conditions and studying some specialgraphs—regular graphs, t-tough graphs, claw-free graphs, quasi-claw-freegraphs and etc.In the recent years, many authors studied the properties on claw-free graphsand obtained many beautiful results. In [2] Ainouche first defined the conceptof quasi-claw-free graphs. Every claw-free graph is quasi-claw-free graph. Andin [2] he extended some results on claw-free graphs to quasi-claw-free graphs.In this paper we obtained some results on quasi-claw-free graphs.We consider only finite undirected graphs without loops and multiple edges.For terminology, notation and concepts not defined here see [1].Let G = (V (G ), E (G ))be a graph, where V (G )and E (G )denote the vertex set andedge set of G respectively.If v ∈ V (G ), then N ( v )denotes the neighborhood set of v in G , andN[v]=N(v)∪{v}.For any two distinct vertices u , v ∈ V (G ), d (u , v ) denotes the distance inG from u and v .A graph G is called claw-free if it contains no induced subgraph isomorphicto K1 ,3.The concept of quasi-claw-free graphs was introduced by Ainouche in [2]. Agraph G is called quasi-claw-free if it satisfies the property:d ( x , y ) = 2? there exists u ∈ N ( x ) ∩ N ( y)such that N (u ) ? N ( x ) ∪ N ( y).Obviouslyevery claw-free graph is quasi-claw-free graph.In chapter 1 we introduce the terminology and notation of graph theoryrelevant to this paper.For 2-connected claw-free graphs, there exists the result:Theorem[3] Let G be 2-connected claw-free graph of order n, if n ≤ 3δ + 2,then G is Hamiltonian.In chapter 2 we extend the result to quasi-claw-free graphs.Theorem Let G be 2-connected quasi-claw-free graph of order n, ifn ≤ 3δ + 2,then G is Hamiltonian.For 3-connected claw-free graphs, there exists the result:Theorem[4] Let G be 3-connected claw-free graph of order n, if n ≤ 5δ ? 5,then G is Hamiltonian.In chapter3 we extend the result to quasi-claw-free graphs.Theorem Let G be 3-connected quasi-claw-free graph of order n, ifn ≤ 5δ ? 4,then G is Hamiltonian.For k-connected claw-free graphs, there exists the result:Theorem[2] A k-connected quasi-claw-free graph G ,(k ≥ 2) is Hamilton if( )v Xd v n k∈∑ ≥ ? holds for every independent set X of cardinality (k+1) in G .In chapter 4 we obtain the following result, it weakens the condition of thefront theorem.Theorem A k-connected quasi-claw-free graph G ,(k ≥ 2) is Hamilton if( )v Xd v n k∈∑ ≥ ? holds for every independent set X of cardinality (k+1) in G2.In chapter 5 we obtain the following result, it extends the result of TianFeng in [19] in some given conditions.Theorem if G is 2-connected non-Hamilton and contains a dominating cycle witha vertex v∈V(C),such that dR(v) ≧2,where R=V(G)-V(C) for all dominatingcycle C, then G contains a dominating cycle of length at least 2σ-2.