An Infinite Family of Planar Hypohamiltonian Oriented Graphs

作者：van Aardt Susan A; Burger Alewyn P^*; Frick Marietjie

来源：Graphs and Combinatorics, 2013, 29(4): 729-733.

DOI：10.1007/s00373-012-1165-z

• Hypohamiltonian
• Bihomogeneously traceable
• Oriented graph
• Planar graph

Carsten Thomassen asked in 1976 whether there exists a planar hypohamiltonian oriented graph. We answer his question by presenting an infinite family of planar hypohamiltonian oriented graphs, the smallest of which has order 9. A computer search showed that 9 is the smallest possible order of a hypohamiltonian oriented graph.

• 出版日期2013-7