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 ≥ k ≥ 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.
|Number of pages||8|
|Journal||Electronic Journal of Graph Theory and Applications|
|Publication status||Published - 2016|
- Broken crown
- Graph construction
- Hamiltonian cycles