TOPICS
Search

Planar Hypotraceable Graph


PlanarHypotraceableGraphs

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 n such that a cubic planar hypotraceable graph exists for every even integer >=n, and Araya and Wiener (2011) settled the question with n=356.


See also

Hamilton-Connected Graph, Hypotraceable Graph, Planar Graph, Planar Hypohamiltonian Graph, Thomassen Graphs, Traceable Graph, Wiener-Araya Graph, Zamfirescu Graphs

Explore with Wolfram|Alpha

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.

Cite this as:

Weisstein, Eric W. "Planar Hypotraceable Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PlanarHypotraceableGraph.html

Subject classifications