Let G be a 2 connected simple graph of order n ( n ≥5) and minimum degree δ . In this paper, we show that if for any two nonadjacent vertices u , v of G there holds | N(u)∪N(v)|≥n-δ , t...Let G be a 2 connected simple graph of order n ( n ≥5) and minimum degree δ . In this paper, we show that if for any two nonadjacent vertices u , v of G there holds | N(u)∪N(v)|≥n-δ , then G is {3,4} - vertex pancyclic unless G≌K n2,n2 .展开更多
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 be a 2 connected simple graph with order n (n≥6) and minimum degree δ . This paper proves that if for any independent set of three vertices { u,v,w} V(G ) there always exist x and y∈{u,...Let G be a 2 connected simple graph with order n (n≥6) and minimum degree δ . This paper proves that if for any independent set of three vertices { u,v,w} V(G ) there always exist x and y∈{u,v,w } such that | N(x)∪N(y)|≥n-δ+1 , then 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.展开更多
Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Ba...Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Basing on which, we has proved that in generalized hypercubes, every edge can be contained on a cycle of every length from 3 to IV（G）I inclusive and all kinds of length cycles have been constructed. The edgepanciclieity and node-pancilicity of generalized hypercubes can be applied in the topology design of computer networks to improve the network performance.展开更多
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 .展开更多
In this paper,we prove that there does not exist an r-UPC[2]-graph for each r≥5 and there does not exist an r-UPC[C_t^2]-graph for each r≥3,where t is the number of bridges in a graph and C_t^2 is the number of comb...In this paper,we prove that there does not exist an r-UPC[2]-graph for each r≥5 and there does not exist an r-UPC[C_t^2]-graph for each r≥3,where t is the number of bridges in a graph and C_t^2 is the number of combinations of t bridges taken 2 at a time.展开更多
Let G be a 2 connected graph with n vertices. In this paper, we prove that if there exist two vertices of any there independent vertices in G such that the sum of whose degree is at least n , then G ...Let G be a 2 connected graph with n vertices. In this paper, we prove that if there exist two vertices of any there independent vertices in G such that the sum of whose degree is at least n , then G is pancyclic, or G is K n/2,n/2 , or G is K n/2,n/2 -e , or G is a cycle of length 5.展开更多
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 G=(V, E) be a hamiltonian K 1.3 free graph such that d(x) |V| 2 and G is connected for some vertex x of G . Then G is pancyclic with a few number of exceptions.
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.展开更多
文摘Let G be a 2 connected simple graph of order n ( n ≥5) and minimum degree δ . In this paper, we show that if for any two nonadjacent vertices u , v of G there holds | N(u)∪N(v)|≥n-δ , then G is {3,4} - vertex pancyclic unless G≌K n2,n2 .
文摘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 be a 2 connected simple graph with order n (n≥6) and minimum degree δ . This paper proves that if for any independent set of three vertices { u,v,w} V(G ) there always exist x and y∈{u,v,w } such that | N(x)∪N(y)|≥n-δ+1 , then 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.
基金This project is supported by National Natural Science Foundation of China （10671081）
文摘Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Basing on which, we has proved that in generalized hypercubes, every edge can be contained on a cycle of every length from 3 to IV（G）I inclusive and all kinds of length cycles have been constructed. The edgepanciclieity and node-pancilicity of generalized hypercubes can be applied in the topology design of computer networks to improve the network performance.
文摘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 .
文摘In this paper,we prove that there does not exist an r-UPC[2]-graph for each r≥5 and there does not exist an r-UPC[C_t^2]-graph for each r≥3,where t is the number of bridges in a graph and C_t^2 is the number of combinations of t bridges taken 2 at a time.
文摘Let G be a 2 connected graph with n vertices. In this paper, we prove that if there exist two vertices of any there independent vertices in G such that the sum of whose degree is at least n , then G is pancyclic, or G is K n/2,n/2 , or G is K n/2,n/2 -e , or G is a cycle of length 5.
文摘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 G=(V, E) be a hamiltonian K 1.3 free graph such that d(x) |V| 2 and G is connected for some vertex x of G . Then G is pancyclic with a few number of exceptions.
文摘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.
