Graph powers and \(k\)-ordered hamiltonicity (Q932592)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph powers and \(k\)-ordered hamiltonicity |
scientific article |
Statements
Graph powers and \(k\)-ordered hamiltonicity (English)
0 references
11 July 2008
0 references
A simple graph \(G\) is \(k\)-ordered Hamiltonian if for any sequence \(v_1, v_2, \dots, v_k\) of \(k\) vertices of \(G\) there is a Hamiltonian cycle in \(G\) containing these vertices in the given order. Let \(H\) be a connected graph with at least \(k\) vertices, \(k \geq 4\). The author proves that \(H^{ \lfloor 3k/2 \rfloor - 2}\) is \(k\)-ordered Hamiltonian. The result is proved to be sharp by establishing a universal lower bound on the smallest power of the path that is \(k\)-ordered Hamiltonian. The k-ordered Hamiltonicity of powers of the cycle of \(n\) vertices is discussed.
0 references
graph powers
0 references
k-ordered Hamiltonian
0 references
Hamiltonian cycles
0 references