Wiener-Araya Graph


The Wiener-Araya graph (Wiener and Araya 2009) is the 42-vertex graph illustrated above that was the smallest known example of a planar hypohamiltonian graph, beating the previous minimal example of the 48-Zamfirescu graph, until the discovery of 25 such graphs on 40 vertices in 2013 (Jooyandeh et al. 2107). The title of the preprint (Weiner and Araya 2009) announcing its discovery ("The Ultimate Question") is a reference to its vertex count, 42, which according to the novel The Hitchhiker's Guide to the Galaxy (Adams 1997), is the ultimate answer to life, the universe, and everything.

The Wiener-Araya graph is implemented in the Wolfram Language as GraphData["WienerArayaGraph"].

See also

42, Araya-Wiener Graphs, Hatzel Graph, Hypohamiltonian Graph, Hypotraceable Graph, Planar Graph, Thomassen Graphs, Zamfirescu Graphs

Explore with Wolfram|Alpha


Adams, D. The Hitchhiker's Guide to the Galaxy. New York: Ballantine Books, 1997.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.Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009., G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th. 67, 55-68, 2011.

Cite this as:

Weisstein, Eric W. "Wiener-Araya Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications