| All graphs considered in this paper are finite, undirected and simple.Let G=(V(G), E(G)) be a graph, where V(G) and E(G) denote the vertex set and edge set of G respectively. For S V(G),vie let (S) denote the subgraph of G induced by S. We denote by E(S) the edge set of (S). If E(S)=Φ, then S is said to be an independent set. The cardinality of a maximum independent set in G is denoted by a. By δ(G), we mean the minimum degree of G. If for every u ∈ V(G)\S,x ∈ S, such that ux∈E(G), then S is said to be a dominating set of G, in particular, if S={v}, then v is called a complete dominating vertex in G. The cardinality of a minimum dominating set in G is denoted by r(G).If r(G)is not connected} is an independent set and for any v ∈ D(g), there exists an u in V(G) such that is connected . If there exists a locally connected u in V(G),such that is connected then G is called weakly locally connected.If D(g) = Φ, then we say G is locally connected.Let H be an induced subgraph G .Then we say H is a p-claw of G if H is isomorphic to Kl,p,while we call the p-degree vertex of G is the clawcenter of the p-claw. Let B(G) to denote the set of all claw centers in G . If p=3 and B(G) =Φ, G is called a claw-free graph. If H is a p-claw of G whose claw center is v, and there do not exist a (p+1)-claw of G whose claw center is v, then H is said to be a maximal p-claw. By Bp and AP, we mean all claw centers of p-claw and of maximal p-claw in G.Kl,p-constructed subgraph sets in G refer to such subgraph that satisfies K=H0+(H1 ∪H2 ∪...∪HP)= H0+( Hi) , where Hi are completeand |V(H0)|>p u,v∈F(H0),satisfiesN(u)\{v}=N(v)\{u} = (V(H0)\{u ,v})U( Hi).A maximal 3-claw in G with the claw center v is said to be a controlled 3-claw, if it satisfies the following:while is 2-dominated; while has either at least two complete dominating vertices or there exist x, x2 ∈ N(v)\B3 , such that x,x2∈ E(G),and for every w∈N(v) \{x1, x2}, w is adjacent to one of x1 and x2.A maximal 3-claw in G with the claw center v is called to be a strong controlled 3-claw, if it satisfies the following:< N(v)> is strong 2-dominated , that is, there exist x1,x2 ∈ N(v)\ B3 , such that x1x2∈ E(G),and for every w∈N(v)\{x1, x2}, w is adjacent to one of x1 and x2.Suppose that M is a maximal p-claw in G with the claw center v0(P>4), where V (M) ={v0, v1, v2......vp }. If there exist Kl,p-constructedsubgraph sets in G, such that vi∈ V(Hi) ,i=0, 1, 2,......p, thenM is said to be a controlled p-claw. All the controlled 3-claws and controlled p-claws (p>4) are simply said to be controlled claw. While strong controlled 3-claw and controlled p-claw (p>4) are called to be strong controlled claw. If all the maximal claws are controlled claws in G, then G is said to be a Kl, P-controlled graph, and if all maximal claws are strong controlled claws in G, then G is said to be a strong Kl,P-controlled graphoG is said to be distance claw-free, if a≤2, for every v∈ V(G) and for every i≥1. Apparently DC C.We say that G is fully cycle extendable if each vertex of G is on a triangle, and for every cycle C with |V(C)| < |V(G)|there is a cycle C', such that V(C) V(C') and |V (C')| = |V (C)| + 1.If P=v1v2...vp is a (u, v) -path in G (u=v1, v=vp), then the length ofpath P refers to the number of the edges in P. For a graph G, if for anytwo distinct vertices u, v and a nonhamilon (u, v) -path P, if there is a(u,v) -path P', satisfying V (P) V(P'), and|P'| = |P|+1, then the graphG is called a path extendable graph.Hamilton problem is one of fundamental problems in graph theory, and it is mainly focused on the cycle problem and the path problem, which containing Hamilton cycle, cycle extensibility, longest cycle and Hamilton path, Hamilton-connectivity, panconnectivity, path extensibility, longest path and so on. As to Hamilton cycle problem, alot of results have been obtained. In 1952, Dirac gave the minimum degree condition on the existence... |
PDF Full Text Request