Planar Hypotraceable Graph

A planar hypotraceable graph is a hypotraceable graph that is also planar. A number of planar hypotraceable graphs are illustrated above.

Using a theorem of Thomassen (1974), the Wiener-Araya graph on 42 vertices can be used to construct a planar hypotraceable graph on 162 vertices, smaller than the 186-vertex graph obtained from the 48-Zamfirescu graph using Thomassen's construction. These graphs are implemented in the Wolfram Language as GraphData["PlanarHypohamiltonian", 162] and GraphData["PlanarHypohamiltonian", 186], respectively.

Jooyandeh et al. (2017) showed that there exist planar hypotraceable graphs on 154 vertices, as well as on all vertex counts greater than or equal to 156.

Using the 70-node Araya-Wiener graph, a 340-node cubic planar hypotraceable graph can be constructed (Araya and Wiener 2011).

Holton and Sheehan (1993) asked if there exists an integer  such that a cubic planar hypotraceable graph exists for every even integer , and Araya and Wiener (2011) settled the question with .

REFERENCES

Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2001.

 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 239-240, 1976.

Grotschel, M. "On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations Res. 5, 285-292, 1980.

Grünbaum, B. "Vertices Missed by Longest Paths or Circuits." J. Combin. Th. A 17, 31-38, 1974.

Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.

Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices." J. Graph Th. 84, 121-133, 2017.

Kapoor, S. F.; Kronk, H. V.; and Lick, D. R. "On Detours in Graphs." Canad. Math. Bull. 11, 195-201, 1968.

Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.

Walter, H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen." J. Combin. Th. 6, 1-6, 1969.

Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009.

 http://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypotraceable Graphs." J. Graph Th. 67, 55-68, 2011.