Premium
Systematic searches for hypohamiltonian graphs
Author(s) -
Collier J. B.,
Schmeichel E. F.
Publication year - 1978
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230080303
Subject(s) - combinatorics , cubic graph , mathematics , induced subgraph , vertex (graph theory) , symmetric graph , discrete mathematics , factor critical graph , distance hereditary graph , graph , line graph , graph power , voltage graph
A graph G is called hypohamiltonian if G is not hamiltonian but every vertex‐deleted subgraph G‐v is hamiltonian. The existence of a p‐vertex hypohamiltonian graph is open only for p = 14,17, and the existence of a p‐vertex, cubic hypohamiltonian graph is open only for p = 14,16,24,32. With the aid of a computer we have established that there is no hypohamiltonian graph of order 14, and no cubic hypohamiltonian graph of order 14 or 16. In addition, there is no hypohamiltonian graph of order 17 with girth ≥ 5. On the other hand, new p‐vertex, cubic hypohamiltonian graphs have been found for p = 18,22.