Let G be a graph, an independent set Y in G is called an essential independent set (or essential set for simplicity), if there is {y 1,y 2} Y such that dist (y 1,y 2)=2. In this paper, we wi...Let G be a graph, an independent set Y in G is called an essential independent set (or essential set for simplicity), if there is {y 1,y 2} Y such that dist (y 1,y 2)=2. In this paper, we will use the technique of the vertex insertion on l connected ( l=k or k+1,k≥2 ) claw free graphs to provide a unified proof for G to be hamiltonian or 1 hamiltonian, the sufficient conditions are expressed by the inequality concerning ∑ki=0N(Y i) and n(Y) for each essential set Y={y 0,y 1,...,y k} of G , where Y i={y i,y i-1 ,...,y i-(b-1) }Y for i∈{0,1,...,k} (the subscriptions of y j ’s will be taken modulo k+1 ), b ( 0【b【k+1 ) is an integer, and n(Y)={v∈V(G): dist (v,Y)≤2 }.展开更多
A graph G is claw\|free if G has no induced subgraph isomorphic to K\-\{1,3\}. And a graph G is pancyclic if for every m, 3≤m≤|V(G)|, there is a cycle of length m. This paper considered neighbourhood union for any p...A graph G is claw\|free if G has no induced subgraph isomorphic to K\-\{1,3\}. And a graph G is pancyclic if for every m, 3≤m≤|V(G)|, there is a cycle of length m. This paper considered neighbourhood union for any pair of nonadjacent vertices in claw\|free graph and obtained the following theorem: If G is a 2\|connected claw\|free graph of order n≥12 and |N(u)∪N(v)|+|N(u)∪N(w)|+|N(v)∪N(w)|≥2n-1 for any three pairwise nonadjacent vertices u,v, and w, then G is pancyclic.展开更多
文摘Let G be a graph, an independent set Y in G is called an essential independent set (or essential set for simplicity), if there is {y 1,y 2} Y such that dist (y 1,y 2)=2. In this paper, we will use the technique of the vertex insertion on l connected ( l=k or k+1,k≥2 ) claw free graphs to provide a unified proof for G to be hamiltonian or 1 hamiltonian, the sufficient conditions are expressed by the inequality concerning ∑ki=0N(Y i) and n(Y) for each essential set Y={y 0,y 1,...,y k} of G , where Y i={y i,y i-1 ,...,y i-(b-1) }Y for i∈{0,1,...,k} (the subscriptions of y j ’s will be taken modulo k+1 ), b ( 0【b【k+1 ) is an integer, and n(Y)={v∈V(G): dist (v,Y)≤2 }.
基金Supported by the National Natural Science Foundationof China(No.196 710 5 0 )
文摘A graph G is claw\|free if G has no induced subgraph isomorphic to K\-\{1,3\}. And a graph G is pancyclic if for every m, 3≤m≤|V(G)|, there is a cycle of length m. This paper considered neighbourhood union for any pair of nonadjacent vertices in claw\|free graph and obtained the following theorem: If G is a 2\|connected claw\|free graph of order n≥12 and |N(u)∪N(v)|+|N(u)∪N(w)|+|N(v)∪N(w)|≥2n-1 for any three pairwise nonadjacent vertices u,v, and w, then G is pancyclic.
