Graph powers and k-ordered Hamiltonicity
| dc.creator | Chebikin, Denis | |
| dc.date | 2003-07-28 | |
| dc.date.accessioned | 2026-07-07T04:59:55Z | |
| dc.date.available | 2026-07-07T04:59:55Z | |
| dc.description | It is known that if G is a connected simple graph, then G^3 is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v_1, v_2, ..., v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that G^(3k/2 + 1) is k-ordered Hamiltonian for a connected graph G on at least k vertices. We further show that if G is connected, then G^4 is 4-ordered Hamiltonian and that if G is Hamiltonian, then G^3 is 5-ordered Hamiltonian. We also give bounds on the smallest power p_k such that G^p_k is k-ordered Hamiltonian for G=P_n and G=C_n. | |
| dc.description | 18 pages, 8 figures; submitted to J. Graph Theory | |
| dc.identifier | https://arxiv.org/abs/math/0307359 | |
| dc.identifier | http://arxiv.org/abs/math/0307359 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/68187 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C45; 05C12; 05C38 | |
| dc.title | Graph powers and k-ordered Hamiltonicity | |
| dc.type | text |