Hamiltonian cycles with all small even chords
Hamiltonian cycles with all small even chords
复制标题
DOI：
10.1016/j.disc.2011.12.013
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
Guantao Chen;K. Ota;Akira Saito;Yi Zhao
中科院分区：
文献类型：
--
作者：
Guantao Chen;K. Ota;Akira Saito;Yi Zhao
设G是阶数n≥3的图. G的偶平方Hamilton圈（ESHC）是G的一个Hamilton圈C= v1 v2. vnv 1，其中对于所有1≤i≤n，弦为vivi+3（其中vn+j= vj，j≥1）.当n是偶数时，ESHC包含所有n阶二部2-正则图。证明了存在一个正整数N，使得对任意偶数阶n≥N的图G，若最小度δ（G）≥n2+92，则G包含一个ESHC.我们证明了n是偶数的条件不能被丢弃，常数92不能被1代替。我们的结果可以很容易地推广到所有k≥2的偶数次幂Hamilton圈。
Let G be a graph of order n≥3. An even squared Hamiltonian cycle (ESHC) of G is a Hamiltonian cycle C=v1v2…vnv1of G with chords vivi+3for all 1≤i≤n (where vn+j=vjfor j≥1). When n is even, an ESHC contains all bipartite 2-regular graphs of order n. We prove that there is a positive integer N such that for every graph G of even order n≥N, if the minimum degree is δ(G)≥n2+92, then G contains an ESHC. We show that the condition of n being even cannot be dropped and the constant 92 cannot be replaced by 1. Our results can be easily extended to evenkth powered Hamiltonian cycles for all k≥2.