PreprintCC BY 4.0arXiv
Enumerating Hamiltonian Paths and Cycles
Abstract
We prove counting formulae for the number of directed Hamiltonian paths and directed Hamiltonian cycles in any complete multipartite graph. The method is based on a collapsing technique relating general path graphs with coloured vertices to legally coloured path graphs.
Related
- Alternating Hamilton Paths and Cycles in Poset Products
- The game chromatic number of generalized Mycielski graphs of paths and cycles
- A Chvátal-type codegree condition for Hamiltonian cycles in k-uniform hypergraphs
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- On the Number of Hamiltonian Cycles in a Boolean Cube
BibTeX
@misc{hylock2026enumerating,
title = {{Enumerating Hamiltonian Paths and Cycles}},
author = {Harry Hylock and Karl Michael Schmidt and Matthew C. Lettington},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06644},
eprint = {2610.06644},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06644},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Enumerating Hamiltonian Paths and Cycles
AU - Harry Hylock
AU - Karl Michael Schmidt
AU - Matthew C. Lettington
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06644
UR - https://arxiv.org/abs/2610.06644
AB - We prove counting formulae for the number of directed Hamiltonian paths and directed Hamiltonian cycles in any complete multipartite graph. The method is based on a collapsing technique relating general path graphs with coloured vertices to legally coloured path graphs.
ER -