Graph equation for line graphs and m-step graphs
Seog-Jin KIM
Department of Mathematics Education,Konkuk University,Seoul143-701,Korea Suh-Ryung KIM∗and Jung Yeun LEE∗
Department of Mathematics Education,Seoul National University
Seoul151-742,Korea
Won Jin PARK†
Department of Mathematics,Seoul National University,Seoul151-742,Korea电影八佰观后感
Yoshio SANO
Rearch Institute for Mathematical Sciences,Kyoto University,606-8502,Japan
Abstract
Given a graph G,the m-step graph of G,denoted by S m(G),has the same vertex t as G and an edge between two distinct vertices u and v if there is
双向箭头a walk of length m from u to v.The line graph of G,denoted by L(G),is a
graph such that the vertex t of L(G)is the edge t of G and two vertices
u and v of L(G)are adjacent if the edges corresponding to u and v share a
common end vertex in G.In this paper,we characterize connected graphs G
satisfying graph equation S m(G)=L(G).
Key words and phras:graph equations,m-step graphs,line graphs
听心的声音1Introduction
关于少先队的手抄报Throughout this paper,we only consider simple graphs.Given a graph G,the following two notions of well-known graphs can be defined:The m-step graph of G, denoted by S m(G),has the same vertex t as G and an edge between two vertices u and v if there is a walk of length m from u to v.The line
graph of G,denoted by L(G),is the interction graph of the edge t of G.That is,the line graph of G is a graph such that the vertex t of L(G)is the edge t of G and two vertices u and v of L(G)are adjacent if the edges corresponding to u and v share a common end vertex in G.For all undefined graph-theoretical terms,e[2].
∗The authors thank KOSEF for its support under grant Com2MaC-KOSEF.
†ail address:
1
Graph equations are equations in which the unknowns are graphs.Since many problems and results in graph theory can be formulated in terms of graph equations, graph equations have been studied by many authors(e[3]for surveys of the literature of graph equations).Especially,graph equations eking a solution graph G who line graph L(G)is isomorphic to another graph structure built from G have been widely studied.For example,Akiyama et al.[1]studied graph equations for line graphs and n th power graphs and Simi´c[6]studied graph equations for line graphs and n th distance graphs.The authors may refer to[4]and[7]for the work on S m(G).
In this paper,we study graph equation for line graphs and m-step graphs.We characterize the graphs who m-step graphs and who line graphs are isomorphic. If S m(G)is isomorphic to L(G)for a graph G,we say that G satisfies S m(G)=L(G).
A graph with exactly one cycle is said to be unicyclic.
Proposition1.1.If a connected graph G=(V,E)satisfies S m(G)=L(G),then G is unicyclic.Especially,if m is even,the length of the cycle contained in G is odd. Proof.Since S m(G)=L(G),V(S m(G))=V(L(G)).By definition,|V(S m(G))|= |V|and|V(L(G))|=|E|and so|V|=|E|.Since G is connected,it is true that G contains exactly one cycle C.
Suppo that m is even.If the length n of C is even,then G is a bipartite graph. Then any two vertices the distance between which is odd are disconnected in S m(G) and so S m(G)is disconnected.However,L(G)is still connected and we reach a contradiction.Thus the length of C must be odd.
We call a cycle of length≥4without a chord a hole.Now we prent a simple but uful property of L(G)for a unicyclic graph G:
Proposition1.2.Suppo that a connected graph G is a unicyclic graph having cycle C=v0e1v1···v n−1e n v0for n≥5.Then L(G)has a unique hole e1e2···e n e1. Proof.Since C is a hole,it is true that e1e2···e n e1is a hole in L(G).If f1f2···f m is a hole in L(G),then x0x1···x m−1x0is a hole in G where x i−1and x i are the end vertices of f i for i=1,...,m.(Identify x m with x0).Since C is the only cycle of G,we have m=n and x i=v i for i=0,...,n−1.Thus L(G)has a unique hole, which has length n.
Note that E(S m(G))⊂E(S m+2(G))for any positive integer m.To e why,take an edge e=xy in S m(G).Then there exists an(x,y)-walk W of length m in G. Let z be the vertex immediately preceding y in W.Then W zy is an(x,y)-walk of length m+2.Thus e is an edge of S m+2(G).
2
We denote by d G(u,v)the distance between u and v in a connected graph G and by diam(G)the diameter of G.
青岛教师Lemma1.3.Suppo that G is a connected unicyclic graph with diam(G)≥4. Then diam(S m(G))≤diam(G)−2for odd m≥3.
Proof.Take two vertices u,v in G.Since E(G)⊂E(S m(G))as noted above,we have d S m(G)(u,v)≤d G(
u,v).If d G(u,v)≤2,then d S m(G)(u,v)≤d G(u,v)≤2≤diam(G)−2.Now suppo that d G(u,v)≥3.Let uv1v2···v l−1v(Identify v l with v.) be a shortest(u,v)-path in G.Then l≥3,and u and v3are adjacent in S m(G)since m is odd.Therefore,d S m(G)(u,v)≤d G(u,v)−2.Thus,d S m(G)(u,v)≤diam(G)−2 for any u,v in G and so diam(S m(G))≤diam(G)−2.
Given a cycle C of a connected graph G,we call a path of G C-avoiding path if its internal vertices are not on C.A spiked cycle is a connected graph who non-pendant vertices form a cycle.
For a vertex v of a graph G,we denote by N G(v)(resp.N G[v])the t of vertices adjacent to v in G(resp.the t of v and vertices adjacent to v in G)or the subgraph of G induced by the tho adjacent vertices.
Theorem1.4.Let m be an odd integer greater than or equal to3.Then for a connected graph G,G satisfies S m(G)=L(G)if and only if G is either a3-cycle or a4-cycle.
Proof.The‘if’part is obviously true.Now we show the‘only if’part.Since a path of G of length l as an induced subgraph corresponds to a path of L(G)of l−1as an induced subgraph,diam(G)≤diam(L(G))+1.By Proposition1.1,G is unicyclic. If diam(G)≥4,then,by Lemma1.3,diam(L(G))≥diam(G)−1>diam(S m(G)), which contradicts the hypothesis that S m(G)=L(G)
.Thus diam(G)≤3.This implies that G is a spiked cycle with a cycle C of length from3up to7,or a unicyclic graph with a3-cycle C such that only one vertex x on C has degree≥3 and a longest C-avoiding path starting at x is unique and has length2.
If C is a5-cycle,a6-cycle,or a7-cycle,then C is a hole in L(G)while C has a chord in S m(G)since any two vertices at distance3in G are adjacent in S m(G).
If C is a4-cycle,then the degree of each vertex on C is2.For otherwi,there is a vertex v of degree at least3on C,and the neighbors of v on C and a neighbor of v not on C form an independent t of size3in S3(G).Thus the edge clique
cover number of N S
3(G)[v]is at least3.It is impossible for L(G)=S m(G)since it
is known that the edge clique cover number of the clod neighborhood of a vertex in a line graph is at most2.Hence G itlf is4-cycle if C is a4-cycle.
Now consider the ca where C is a3-cycle.Since diam(G)≤3,S m(G)is a complete graph for odd m≥3.If there is a vertex x not on C that is joined to
3
a vertex y on C by an edge e,then e is not adjacent to the edge joining the two vertices on C other than y in L(G).Thus it is impossible that S m(G)=L(G). Therefore G has to be a3-cycle.
Now it remains to characterize a connected graph G satisfying S m(G)=L(G) for an even integer m.We begin by prenting the following theorem:
Theorem1.5.Let G be a connected graph.If S m(G)=L(G)for an even integer m≥4,then the girth of G is3.
Proof.By Proposition1.1,G contains a unique odd cycle C=v0v1···v l−1v0.Sup-po that l≥5.We will reach a contradiction.Since G is C4-free,
|E(L(G))|= v∈V(G) deg G(v)2
where deg G(v)denotes the degree of v in G.
Since E(S2(G))⊂E(S m(G))for even m,S m(G)has at least农村教育
v∈V(G) deg G(v)2 (⋆) edges.However,since C is not a6-cycle,S m(G)contains edge v0v4that is not counted in(⋆).This implies that|E(S m(G))|>|E(L(G))|,which is contradiction. Thus,l≤3.
We have characterized a connected graph G satisfying S m(G)=L(G)for an odd integer m.Now it remains to characterize a connected graph G satisfying S m(G)=L(G)for an even integer m.We consider a connected graph G with girth greater than3in Section2and a connected graph G with girth3in Section3.
王者荣耀虞姬2Graph with girth>3satisfying S m(G)=L(G)for even m Theorem1.5tells us that if a connected graph G with girth greater than3satisfies S m(G)=L(G)for even m,then m=2.Thus,it is sufficient to consider the ca where m=2.
Proposition2.1.Suppo that a connected graph G is a unicyclic graph having cycle C=v0e1v1···v n−1e n v0for n≥5.Then S2(G)and L(G)have unique holes v0v2···v n−1v1v3···v n−2v0and e1e2···e n e1,respectively.
4
君子兰夹箭怎么办Proof.Let C =v 0e 1v 1e 2···v n −1e n v 0(n ≥5).Then delete an edge e n on C from G .Then the resul
ting graph G −e n is a tree.Phelps [5]showed that the 2-step graph of a tree with at least 2vertices has exactly two components and is chordal.It is easy to e that v 0v 2···v n −1and v 1v 3···v n −2are paths of length at least one as induced subgraphs of S 2(G −e n )which belong to different components of S 2(G −e n ).Note that
E (S 2(G ))=E (S 2(G −e n ))∪{xv n −1|x ∈N G (v 0)}∪{yv 0|y ∈N G (v n −1)}.Thus S 2(G )has hole C ∗=v 0v 2···v n −1v 1v 3···v n −2v 0.Any vertex in N G (v 0)(resp.N G (v n −1))other than v 1(resp.v n −2)forms a triangle with v 1and v n −1(resp.v 0and v n −2)in S 2(G ).Hence C ∗is the only hole in S 2(G ).
By Proposition 1.2,L (G )contains a unique hole e 1e 2···e n e 1.
Proposition 2.2.If a connected graph G has girth greater than 3and satisfies S 2(G )=L (G ),then G is a spiked odd cycle.
Proof.By contradiction.Suppo that there is a connected graph G such that S 2(G )=L (G )and G is not a spiked odd cycle.Since S 2(G )=L (G ),there exists a bijection φfrom V (S 2(G ))to V (L (G ))such that uv ∈E (S 2(G ))if and only if φ(u )φ(v )∈E (L (G ))for vertices u ,v in G .By Proposition 1.1,G has a unique odd cycle C =v 0e n −1v n −1e n v 0(n ≥5).Let P =x 1x 2···x k be a longe
st C -avoiding path which shares an initial vertex x 1with C .Then k ≥3by the assumption that G is not a spiked odd cycle.Without loss of generality,we may assume that v 0=x 1.By Proposition 2.1,S 2(G )and L (G )have unique holes C 1=v 0v 2···v n −1v 1v 3···v n −2v 0and C 2=e 1e 2···e n e 1,respectively.Then S 2(G )=L (G )implies that φ(V (C 1))=V (C 2).It is easy to check that
r =max {d S 2(G )(v,w )|v ∈V (C 1),w ∈V (G )\V (C 1)}= d S 2(G )(v 1,x k )if k is odd;d S 2(G )(v 0,x k )if k is even;=n −12+ k 2
and
s =max {d L (G )(e,f )|e ∈V (C 2),f ∈E (G )\V (C 2)}
=d L (G )(e (n +1)/2,x k −1x k )
=n −12
+(k −1).Since φ(V (C 1))=V (C 2),we have r =s .Thus ⌊k/2⌋=k −1.However,k −1>⌊k/2⌋for k ≥3and we reach a contradiction.
5
