Article ID Journal Published Year Pages File Type
4647907 Discrete Mathematics 2012 15 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,