Hamiltonian N2-locally Connected Claw-Free Graphs
Hong-Jian Lai,Yehong Shao and Mingquan Zhan特别追踪
Department of Mathematics
West Virginia University,Morgantown,WV26506
February7,2003
Abstract
A graph G is N2-locally connected if for every vertex v in G,the edges not incident with
v but having at least one end adjacent to v in G induce a connected graph.In1990,Ryj´a˘c ek
愁绪
conjectured that every3-connected N2-locally connected claw-free graph is hamiltonian.This
conjecture is proved in this note.
1Introduction
We u[1]for terminology and notations not defined here,and considerfinite simple graphs only. Let G be a graph.Denote by d G(v)the degree of a vertex v∈V(G).For a vertex v of G,the neighborhood of ,the induced subgraph on the t of all vertices that are adjacent to v, will be called the neighborhood of thefirst type of v in G and denoted by N1(v,G),or briefly, N1(v)or N G(v).For notational convenience,we shall u N G(v)to denote both the induced subgraph and the t of vertices adjacent to v in G.We define the neighborhood of the cond type of v in G(denoted by N2(v,G),or briefly,N2(v))as the subgraph of G induced by the edge subt{e=xy∈E(G):v/∈{x,y}and{x,y}∩N(v)=∅}.We say that a vertex v is locally connected if N(v)is connected;and G is locally connected if every vertex of G is locally connected.Analogously,a vertex v is N2-locally connected if its cond type neighborhood N2(v) is connected;and G is called N2-locally connected if every vertex of G is N2-locally connected.It follows from the definitions that every locally connected graph is N2-locally connected.A graph G is claw-free if it does not contain K1,3as an induced subgraph.The following theorems give the hamiltonicity of the locally and N2-locally connected graph.
Theorem1.1(Oberly and Sumner,[5])Every connected locally connected claw-free graph on at least three vertices is hamiltonian.
Theorem1.2(Ryj´a˘c ek,[7])Let G be a connected,N2-locally connected claw-free graph without vertices of degree1,which does not contain an induced subgraph H isomorphic to either G1or G2(Figure1)such that N1(x,G)of every vertex x of degree4in H is disconnected.Then G is hamiltonian.
1
We say that G is vertex pancyclic if it contains cycles of every length through every vertex.Theorem 1.3(Li,[4])Let G be a connected,N 2-locally connected claw-free graph with δ(G )≥3,which does not contain an induced subgraph H isomorphic to either G 1or G 2(Figure 1).Then G is vertex pancyclic.
d d d d d d d d t t t t t t t t G 1 d d d d d d d d
t t t t t t t t G 2Figure 1
形容树的成语The main purpo of this note is to prove the following theorem,conjectured by Ryj´a ˘c ek in [7].Theorem 1.4Every 3-connected N 2-locally connected claw-free graph is hamiltonian.2Proof of the main theorem
Our approach is to firstly apply the line graph closure (invented by Ryj´a ˘c ek in [8])to convert the pr
oblem into a line graph problem.Then apply techniques in supereulerian graphs to solve the corresponding line graph problem.
垃圾桶的折法The line graph of a graph G ,denoted by L (G ),has E (G )as its vertex t,where two vertices in L (G )are adjacent if and only if the corresponding edges in G are adjacent.Let G be the line graph L (H )of a graph H .If L (H )is k -connected,then H is esntially k -edge-connected,which means that the only edge-cut ts of H having less than k edges are the ts of edges incident with some vertex of H .
In [8],Ryj´a ˘c ek defined the closure cl (G )of a claw-free graph G by recursively completing the neighborhood of any locally connected vertex of G ,as long as this is possible.The closure cl (G )is a well-defined claw-free graph and its connectivity is at least equal to the connectivity of G .The circumference of G is the length of a longest cycle in G .
Theorem 2.1(Ryj´a ˘c ek,[8])Let G be a claw-free graph and cl (G )its closure.Then (i)there is a triangle-free graph H such that cl (G )is the line graph of H ,(ii)both graphs G and cl (G )have the same circumference.
做更好的自己Let O (G )denote the t of all vertices in G with odd degree.A graph G is eulerian if O (G )=∅and G i
s connected.A spanning clod trail of G is called a spanning eulerian subgraph
2
of G.A subgraph H of G is dominating if G−V(H)is edgeless.If a clod trail C of G satisfies E(G−V(C))=∅,then C is called a dominating eulerian subgraph.
Theorem2.2(Harary and Nash-Williams,[2])The line graph G=L(H)of a graph H is hamiltonian if and only if H has a dominating eulerian subgraph.
Theorem2.2reveals the relationship between a dominating eulerian subgraph in H and a hamiltonian cycle in L(H).
Theorem2.3below provides a sufficient condition for a graph to have a spanning eulerian subgraph(therefore a dominating eulerian subgraph),which is originally conjectured by Paulraja ([6]).
Theorem2.3(Lai,[3])Let G be a2-connected graph withδ(G)≥3.If every edge of G is in an m-cycle of G(m≤4),then G has a spanning eulerian subgraph.
Lemma2.4Let G be an N2-locally connected graph and let x be a locally connected vertex of G such
that G[N G(x)]is not complete.Let N ={uv:u,v∈N G(x),uv∈E(G)}and let G be the graph with vertex t V(G )=V(G)and with edge t E(G )=E(G)∪N .Then G is N2-locally connected.
Proof.Let w∈V(G ).If w=x,then N2(w,G )is connected since N G (x)is complete. So we may assume that w=x.Since G is N2-locally connected,N2(w,G)is connected.If E(N2(w,G ))−E(N2(w,G))=∅,then E(N2(w,G ))=E(N2(w,G))and N2(w,G )is connected. Thus we assume that E(N2(w,G ))−E(N2(w,G))=∅.Let e=uv∈E(N2(w,G ))−E(N2(w,G)). Since e=uv∈E(N2(w,G )),we have w∈{u,v},and so uv∈E(G ).Without loss of generality, we assume that wu∈E(G ).
Ca1.uv∈E(G).
By e=uv∈E(N2(w,G)),we have wu,wv∈E(G).Since wu∈E(G )by the assumption, w,u∈N G(x).So xu∈E(N2(w,G)).Therefore adding a new edge uv to N2(w,G)does not change its connectivity,and so N2(w,G )is connected.
Ca2.uv∈E(G).
Since uv∈E(G ),we have u,v∈N G(x).If w∈N G(x),then xu,xv∈E(N2(w,G)). Thus adding a new edge uv to N2(w,G)does not change its connectivity,and so N2(w,G )is connected.If w∈N G(x),then we hav
e wu∈E(G)since wu∈E(G )(otherwi,w∈N G(x),a contradiction).Thus xu∈E(N2(w,G)).So adding a new edge uv to N2(w,G)does not change its connectivity,and therefore N
2(w,G )is connected.
The proof of Theorem1.4.By Theorem2.1(ii),the graph G is hamiltonian if and only if its closure cl(G)is hamiltonian.By Lemma2.4and as cl(G)is both3-connected and claw free, the graph cl(G)is also a3-connected N2-locally connected claw-free graph.By Theorem2.1,we may assume that for a triangle free graph H,G=cl(G)=L(H).
An edge e=uv is called a pendant edge if either d G(u)=1or d G(v)=1.
3
Claim1.Let e=uv∈E(H).If e is not a pendant edge,then e is in some4-cycle of H. Proof.Since H is triangle-free,we have N H(u)∩N H(v)=∅.Let v e∈V(G)correspond to the edge e∈E(H)in terms of the line graph.Since e is not a pendant edge and G is claw free, N G(v e)is the union of two disjoint cliques.Suppo they are L1,L2.Since G is3-connected, there exits at least one path w1w2···w n whi
ch is edge disjoint with G[V(L1)∪V(L2)∪{v e}]in G−v e with w1∈V(L1),w n∈V(L2).Since G is N2-locally connected,we have that n=3.Thus v e w1w2w3v e is an induced4-cycle of G,which corresponds to a4-cycle in H containing e.
Let H be the graph obtained from H by deleting the vertices of degree1or2and replacing each path xyz in H with d H(y)=2by an edge xy.Then it is straightforward to verify the following claim.
Claim2.If H has a spanning eulerian subgraph,then H has a dominating eulerian subgraph.
Since G is3-connected, H is3-edge-connected.Let B be an arbitrary block of H.Since H is3-edge-connected,δ(B)≥3.By Claim1,every edge of B lies in a cycle of B of length at most 4.By Theorem2.3and since B is2-connected,B has a spanning eulerian subgraph.Since every block of H has a spanning eulerian subgraph, H has a spanning eulerian subgraph.By Claim2, H has a dominating eulerian subgraph.By Theorem2.2,cl(G)is hamiltonian.
References
[1]J.A.Bondy and U.S.R.Murty,Graph theory with applications,Macmillan,London and
Elvier,New York,1976.
[2]F.Harary and C.St.J.A.Nash-Williams,On eulerian and hamiltonian graphs and line
爬行的好处
拥挤用英语怎么说graphs,Canad.Math.Bull.8(1965),701-709.
[3]H.-J.Lai,Graph who edges are in small cycles,Discrete Math.94(1991),11-22.
[4]M.Li,On pancyclic claw-free graphs,Ars Combinatoria,To appear.
压力面[5]D.J.Oberly and D.P.Sumner,Every connected,locally connected nontrivial graph with no
induced claw is hamiltonian,J.Graph Theory,3(1979),351-356.
[6]P.Paulraja,On graphs admitting spanning eulerian subgraphs.Ars Combin.24(1987),57-65.
[7]Z.Ryj´a˘c ek,Hamiltonian circuits in N2-locally connected K1,3-free graphs,J.Graph Theory,
14(1990),321-331.
[8]Z.Ryj´a˘c ek,On a closure concept in claw-free graphs,J.Combin.Theory Ser.B,70(1997),
217-224.
4
