The twisted cube TQn is a variant of the hypercube Qn. It has been shown by Chang, Wang and Hsu [Topological properties of twisted cube. Information Science, 113, 147-167 （1999）] that TQn contains a cycle of every l...The twisted cube TQn is a variant of the hypercube Qn. It has been shown by Chang, Wang and Hsu [Topological properties of twisted cube. Information Science, 113, 147-167 （1999）] that TQn contains a cycle of every length from 4 to 2^n. In this paper, we improve this result by showing that every edge of TQn lies on a cycle of every length from 4 to 2^n inclusive. We also show that the twisted cube are Hamiltonian connected.展开更多
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.展开更多
A non-increasing sequenceπ=(d_1,d_2,···,d_n)of nonnegative integers is said to be potentially hamiltonian-graphic(resp.potentially pancyclic-graphic)if it is realizable by a simple graph on n vertices ...A non-increasing sequenceπ=(d_1,d_2,···,d_n)of nonnegative integers is said to be potentially hamiltonian-graphic(resp.potentially pancyclic-graphic)if it is realizable by a simple graph on n vertices containing a hamiltonian cycle(resp.containing cycles of every length from 3 to n).A.R.Rao and S.B.Rao(J.Combin.Theory Ser.B,13(1972),185–191)and Kundu(Discrete Math.,6(1973),367–376)presented a characterization ofπ=(d_1,d_2,···,d_n)that is potentially hamiltonian-graphic.S.B.Rao(Lecture Notes in Math.,No.855,Springer Verlag,1981,417–440,Unsolved Problem 2)further posed the following problem:present a characterization ofπ=(d_1,d_2,···,d_n)that is potentially pancyclic-graphic.In this paper,we first give solution to this problem for the case of 4≤n≤11.Moreover,we also show that a near regular graphic sequenceπ=(d_1,d_2,···,d_n)with dn≥3 is potentially pancyclic-graphic.展开更多
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.
设 e=uv 是 G 中住一条边,e 的次数 d(e)=d(u)+d(v),其中 d(u)和d(u)分别为顶点 u 和 v 在 G 中的度数。本文的主要结果是:设 G 是几乎无桥的,n≥11阶简单连通图,若对任意相距为1的两边 e_0和 e_1,d(e_0)+d(e_1)≥2n-5,则 G 的线图 L(G...设 e=uv 是 G 中住一条边,e 的次数 d(e)=d(u)+d(v),其中 d(u)和d(u)分别为顶点 u 和 v 在 G 中的度数。本文的主要结果是:设 G 是几乎无桥的,n≥11阶简单连通图,若对任意相距为1的两边 e_0和 e_1,d(e_0)+d(e_1)≥2n-5,则 G 的线图 L(G)是泛圈的。展开更多
基金Supported by National Natural Science Foundation of China (Grant No. 10701074)Sciences Foundation for Young Scholars of Beijing Normal University and Priority Discipline of Beijing Normal University
文摘The twisted cube TQn is a variant of the hypercube Qn. It has been shown by Chang, Wang and Hsu [Topological properties of twisted cube. Information Science, 113, 147-167 （1999）] that TQn contains a cycle of every length from 4 to 2^n. In this paper, we improve this result by showing that every edge of TQn lies on a cycle of every length from 4 to 2^n inclusive. We also show that the twisted cube are Hamiltonian connected.
基金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.
基金Supported by National Natural Science Foundation of China(Grant No.11561017)Natural Science Foundation of Hainan Province(Grant No.2016CXTD004)
文摘A non-increasing sequenceπ=(d_1,d_2,···,d_n)of nonnegative integers is said to be potentially hamiltonian-graphic(resp.potentially pancyclic-graphic)if it is realizable by a simple graph on n vertices containing a hamiltonian cycle(resp.containing cycles of every length from 3 to n).A.R.Rao and S.B.Rao(J.Combin.Theory Ser.B,13(1972),185–191)and Kundu(Discrete Math.,6(1973),367–376)presented a characterization ofπ=(d_1,d_2,···,d_n)that is potentially hamiltonian-graphic.S.B.Rao(Lecture Notes in Math.,No.855,Springer Verlag,1981,417–440,Unsolved Problem 2)further posed the following problem:present a characterization ofπ=(d_1,d_2,···,d_n)that is potentially pancyclic-graphic.In this paper,we first give solution to this problem for the case of 4≤n≤11.Moreover,we also show that a near regular graphic sequenceπ=(d_1,d_2,···,d_n)with dn≥3 is potentially pancyclic-graphic.
文摘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.
文摘设 e=uv 是 G 中住一条边,e 的次数 d(e)=d(u)+d(v),其中 d(u)和d(u)分别为顶点 u 和 v 在 G 中的度数。本文的主要结果是:设 G 是几乎无桥的,n≥11阶简单连通图,若对任意相距为1的两边 e_0和 e_1,d(e_0)+d(e_1)≥2n-5,则 G 的线图 L(G)是泛圈的。
