Graph powers and k-ordered Hamiltonicity |
| |
Authors: | Denis Chebikin |
| |
Institution: | Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA |
| |
Abstract: | It is known that if G is a connected simple graph, then G3 is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v1, v2,…,vk of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G⌊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 Pn, we show that this result is sharp. We also give a lower bound on the power of the cycle Cn that guarantees k-ordered Hamiltonicity. |
| |
Keywords: | Graph powers k-Ordered Hamiltonian Hamiltonian cycles |
本文献已被 ScienceDirect 等数据库收录! |
|