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 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 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.展开更多
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.展开更多
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 , 展开更多
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.展开更多
基金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 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 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 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.
文摘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 ,
文摘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.
