Abstract
Let G be a graph of order n<3. An even squared Hamiltonian cycle (ESHC) of G is a Hamiltonian cycle C= v1v2... vn v1 of G with chords vivi+ 3 for all 1≤i≤n (where vn+ j= vj for 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 even kth powered Hamiltonian cycles for all k<2.
Original language | English |
---|---|
Pages (from-to) | 1226-1240 |
Number of pages | 15 |
Journal | Discrete Mathematics |
Volume | 312 |
Issue number | 6 |
DOIs | |
Publication status | Published - 2012 Mar 28 |
Keywords
- Dirac theorem
- Hamiltonian cycle
- Posa's conjecture
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics