Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles
| Main Author: | Haythorpe, Michael; School of Computer Science, Engineering and Mathematics, Flinders University, 1284 South Road, Clovelly Park, SA 5042, Australia |
|---|---|
| Other Authors: | Defence Science and Technology Organisation |
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2016
|
| Subjects: | |
| Online Access: |
http://www.ejgta.org/index.php/ejgta/article/view/97 http://www.ejgta.org/index.php/ejgta/article/view/97/pdf_13 |
Daftar Isi:
- 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$.