This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result ...This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result of Veldman([8]) this result settles the conjecture of Benhocine, et.al([1]): Let G be a connected almost bridgeless graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1). If n is sufficintly large, L(G) is pancyclic.展开更多
Let G={Gi:i∈[n]} be a collection of not necessarily distinct n-vertex graphs with the same vertex set V,where G can be seen as an edge-colored(multi)graph and each Gi is the set of edges with color i.A graph F on V i...Let G={Gi:i∈[n]} be a collection of not necessarily distinct n-vertex graphs with the same vertex set V,where G can be seen as an edge-colored(multi)graph and each Gi is the set of edges with color i.A graph F on V is called rainbow if any two edges of F come from different Gis’.We say that G is rainbow pancyclic if there is a rainbow cycle Cℓof lengthℓin G for each integerℓ2[3,n].In 2020,Joos and Kim proved a rainbow version of Dirac’s theorem:Ifδ(Gi)≥2/n for each i∈[n],then there is a rainbow Hamiltonian cycle in G.In this paper,under the same condition,we show that G is rainbow pancyclic except that n is even and G consists of n copies of Kn/2,n/2.This result supports the famous meta-conjecture posed by Bondy.展开更多
In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id（v）. In this paper, we prove that if G is a 2-connected graph of order n such that id（u） ＋ id（v） ...In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id（v）. In this paper, we prove that if G is a 2-connected graph of order n such that id（u） ＋ id（v） ≥ n for each pair of nonadjacent vertices u and v in G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is isomorphic to F4r .展开更多
Let D be a diagraph of order n≥9 and δ≥n-2. If for every pairof vertices u, v∈V(D) , either uv∈ A(D) or . Theauthor has proved D is pancyclic before. In this paper we suppose n≥6 in-stead of n≥9 in above condit...Let D be a diagraph of order n≥9 and δ≥n-2. If for every pairof vertices u, v∈V(D) , either uv∈ A(D) or . Theauthor has proved D is pancyclic before. In this paper we suppose n≥6 in-stead of n≥9 in above condition, and show the same result holds except 6s展开更多
It is shown that if G is a 2 connected graph on n≥10 vertices such that d(x)+d(y)+d(z)≥3n/2-2 for every triple of vertices x,y,z with min {d(x,y),d(y,z),d(x,z)}=2 , then G is pancyclic or ...It is shown that if G is a 2 connected graph on n≥10 vertices such that d(x)+d(y)+d(z)≥3n/2-2 for every triple of vertices x,y,z with min {d(x,y),d(y,z),d(x,z)}=2 , then G is pancyclic or n is even and G= K n/2 ,展开更多
Let C be a 2-connected graph on > 2 31 venices. G is called pancyclic if itcontains a cycle of length I for every I such that 3 l n. In this paper we shall prove thatif IN(u) U N(v) Z (2n - 3)/3 for any nonadjacent...Let C be a 2-connected graph on > 2 31 venices. G is called pancyclic if itcontains a cycle of length I for every I such that 3 l n. In this paper we shall prove thatif IN(u) U N(v) Z (2n - 3)/3 for any nonadjacent pair uv E V(G), then G is pancyclic.展开更多
Let p be a prime,q be a power of p,and let Fq be the field of q elements.For any positive integer n,the Wenger graph Wn(q)is defined as follows:it is a bipartite graph with the vertex partitions being two copies of th...Let p be a prime,q be a power of p,and let Fq be the field of q elements.For any positive integer n,the Wenger graph Wn(q)is defined as follows:it is a bipartite graph with the vertex partitions being two copies of the(n+1)-dimensional vector space Fq^n+1,and two vertices p=(p(1),…,p(n+1))and l=[l(1),…,l(n+1)]being adjacent if p(i)+l(i)=p(1)l(1)i-1,for all i=2,3,…,n+1.In 2008,Shao,He and Shan showed that for n≥2,Wn(q)contains a cycle of length 2 k where 4≤k≤2 p and k≠5.In this paper we extend their results by showing that(i)for n≥2 and p≥3,Wn(q)contains cycles of length 2k,where 4≤k≤4 p+1 and k≠5;(ii)for q≥5,0<c<1,and every integer k,3≤k≤qc,if 1≤n<(1-c-7/3 logq2)k-1,then Wn(q)contains a 2 k-cycle.In particular,Wn(q)contains cycles of length 2 k,where n+2≤k≤qc,provided q is sufficiently large.展开更多
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.展开更多
gives that every connected,locally connected K 1,4 free,almost claw free graph on at least three vertices is vertices pancyclic. This paper shows that every connected,locally 2 connected K 1,4 fr...gives that every connected,locally connected K 1,4 free,almost claw free graph on at least three vertices is vertices pancyclic. This paper shows that every connected,locally 2 connected K 1,4 free claw centre independent graph on at least three vertices is vertex pancyclic.展开更多
文摘This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result of Veldman([8]) this result settles the conjecture of Benhocine, et.al([1]): Let G be a connected almost bridgeless graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1). If n is sufficintly large, L(G) is pancyclic.
基金supported by the National Natural Science Foundation of China(No.12131013,No.12161141006 and No.12201375)the Tianjin Research Innovation Project for Postgraduate Students(No.2022BKY039).
文摘Let G={Gi:i∈[n]} be a collection of not necessarily distinct n-vertex graphs with the same vertex set V,where G can be seen as an edge-colored(multi)graph and each Gi is the set of edges with color i.A graph F on V is called rainbow if any two edges of F come from different Gis’.We say that G is rainbow pancyclic if there is a rainbow cycle Cℓof lengthℓin G for each integerℓ2[3,n].In 2020,Joos and Kim proved a rainbow version of Dirac’s theorem:Ifδ(Gi)≥2/n for each i∈[n],then there is a rainbow Hamiltonian cycle in G.In this paper,under the same condition,we show that G is rainbow pancyclic except that n is even and G consists of n copies of Kn/2,n/2.This result supports the famous meta-conjecture posed by Bondy.
文摘In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id（v）. In this paper, we prove that if G is a 2-connected graph of order n such that id（u） ＋ id（v） ≥ n for each pair of nonadjacent vertices u and v in G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is isomorphic to F4r .
文摘Let D be a diagraph of order n≥9 and δ≥n-2. If for every pairof vertices u, v∈V(D) , either uv∈ A(D) or . Theauthor has proved D is pancyclic before. In this paper we suppose n≥6 in-stead of n≥9 in above condition, and show the same result holds except 6s
文摘It is shown that if G is a 2 connected graph on n≥10 vertices such that d(x)+d(y)+d(z)≥3n/2-2 for every triple of vertices x,y,z with min {d(x,y),d(y,z),d(x,z)}=2 , then G is pancyclic or n is even and G= K n/2 ,
文摘Let C be a 2-connected graph on > 2 31 venices. G is called pancyclic if itcontains a cycle of length I for every I such that 3 l n. In this paper we shall prove thatif IN(u) U N(v) Z (2n - 3)/3 for any nonadjacent pair uv E V(G), then G is pancyclic.
基金supported by NSF grant DMS-1106938-002,NSFC(Nos.11701372.11801371)Shanghai Sailing Program(No.19YF1435500).
文摘Let p be a prime,q be a power of p,and let Fq be the field of q elements.For any positive integer n,the Wenger graph Wn(q)is defined as follows:it is a bipartite graph with the vertex partitions being two copies of the(n+1)-dimensional vector space Fq^n+1,and two vertices p=(p(1),…,p(n+1))and l=[l(1),…,l(n+1)]being adjacent if p(i)+l(i)=p(1)l(1)i-1,for all i=2,3,…,n+1.In 2008,Shao,He and Shan showed that for n≥2,Wn(q)contains a cycle of length 2 k where 4≤k≤2 p and k≠5.In this paper we extend their results by showing that(i)for n≥2 and p≥3,Wn(q)contains cycles of length 2k,where 4≤k≤4 p+1 and k≠5;(ii)for q≥5,0<c<1,and every integer k,3≤k≤qc,if 1≤n<(1-c-7/3 logq2)k-1,then Wn(q)contains a 2 k-cycle.In particular,Wn(q)contains cycles of length 2 k,where n+2≤k≤qc,provided q is sufficiently large.
基金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.
基金Supported by the Science Foundation of Tsinghua University
文摘gives that every connected,locally connected K 1,4 free,almost claw free graph on at least three vertices is vertices pancyclic. This paper shows that every connected,locally 2 connected K 1,4 free claw centre independent graph on at least three vertices is vertex pancyclic.
