Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647907 | Discrete Mathematics | 2012 | 15 Pages |
Abstract
Let GG be a graph of order n≥3n≥3. An even squared Hamiltonian cycle (ESHC) of GG is a Hamiltonian cycle C=v1v2…vnv1C=v1v2…vnv1 of GG with chords vivi+3vivi+3 for all 1≤i≤n1≤i≤n (where vn+j=vjvn+j=vj for j≥1j≥1). When nn is even, an ESHC contains all bipartite 22-regular graphs of order nn. We prove that there is a positive integer NN such that for every graph GG of even order n≥Nn≥N, if the minimum degree is δ(G)≥n2+92, then GG contains an ESHC. We show that the condition of nn being even cannot be dropped and the constant 9292 cannot be replaced by 11. Our results can be easily extended to even kkth powered Hamiltonian cycles for all k≥2k≥2.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Guantao Chen, Katsuhiro Ota, Akira Saito, Yi Zhao,