Electronic Journal of Graph Theory and Applications (Apr 2016)

Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

  • Michael Haythorpe

DOI
https://doi.org/10.5614/ejgta.2016.4.1.3
Journal volume & issue
Vol. 4, no. 1
pp. 18 – 25

Abstract

Read online

A constructive method is provided that outputs a directed graph which is named a broken crown graph, containing $5n-9$ vertices and $k$ Hamiltonian cycles for any choice of integers $n \geq k \geq 4$. The construction is not designed to be minimal in any sense, but rather to ensure that the graphs produced remain non-trivial instances of the Hamiltonian cycle problem even when $k$ is chosen to be much smaller than $n$.

Keywords