Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650545 | Discrete Mathematics | 2008 | 10 Pages |
Abstract
It is known that if G is a connected simple graph, then G3G3 is Hamiltonian (in fact, Hamilton-connected). A simple graph is k -ordered Hamiltonian if for any sequence v1v1, v2,…,vkv2,…,vk of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k⩾4k⩾4, then G⌊3k/2⌋-2G⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph PnPn, we show that this result is sharp. We also give a lower bound on the power of the cycle CnCn that guarantees k-ordered Hamiltonicity.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Denis Chebikin,