TOPICS
Search

Hypohamiltonian Graph


A graph G is hypohamiltonian if G is nonhamiltonian, but G-v is Hamiltonian for every v in V (Bondy and Murty 1976, p. 61). The Petersen graph, which has ten nodes, is the smallest hypohamiltonian graph (Herz et al. 1967; Bondy and Murty 1976, p. 61) and the only such graph on ten nodes. Herz et al. (1967) showed that there are no hypohamiltonian graphs with 11 or 12 vertices.

By parity, no bipartite graph is hypohamiltonian. Many (but not all) snarks are hypohamiltonian.

Hypohamiltonian graphs are almost Hamiltonian.

Zamfirescu (2019) showed that every singlecross hypohamiltonian graph contains a cubic vertex (Tsai 2024).

HypohamiltonianFamily6

The Lindgren-Sousselier graphs are a sequence of hypohamiltonian graphs on 6k+10 vertices constructed independently by Sousselier (in Herz et al. 1967) and Lindgren (1967).

Bondy (1972) found an infinite sequence of hypohamiltonian graphs on 12k+10 vertices.

Sousselier found a cubic hypohamiltonian graph on 18 vertices (Chvátal 1973). Chvátal (1973) showed there exists a hypohamiltonian graph on p vertices for every p>=26. More generally, there exists a hypohamiltonian graph for every p>=13 with the exception of p=14 (Collier and Schmeichel 1978) and p=17 (Aldred et al. 1997). Aldred et al. (1997) give a complete enumeration of all (seven) hypohamiltonian graphs on 17 or fewer vertices. McKay gives a listing of all known hypohamiltonian graphs up to 26 vertices (where the enumerations on 18 vertices and higher may be incomplete), as well as a girth-restricted subset of cubic hypohamiltonian up to 26 vertices. The numbers of hypohamiltonian graphs on n=1, 2, ... nodes are 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 4, 0, 14, 34, ... (OEIS A141150; Goedgebeur and Zamfirescu 2017).

Thomassen (1973) found hypohamiltonian graphs on p=20 and 25 vertices, and Collier and Schmeichel (1978) found "new" hypohamiltonian graphs for p=18 and 22, though their "new" p=18 graph is actually isomorphic to the first Blanuša snark and their "new" p=22 graphs are isomorphic to the Loupekine snarks.

HypohamiltonianGraphs

A number of non-snark hypohamiltonian graphs, including a number previously discussed, are shown above, ordered by vertex count.

Planar hypohamiltonian graphs are a class of hypotraceable graphs of special interest (Jooyandeh et al. 2017).

The following table summarizes some named hypohamiltonian graphs (including snarks) on 50 or fewer vertices.


See also

Almost Hamiltonian Graph, Almost Hypohamiltonian Graph, Araya-Wiener Graphs, Cubic Planar Hypohamiltonian Graph, Hamiltonian Graph, Hatzel Graph, Hypotraceable Graph, Lindgren-Sousselier Graph, Petersen Graph, Planar Hypohamiltonian Graph, Snark, Traceable Graph, Wiener-Araya Graph, Zamfirescu Graphs

Explore with Wolfram|Alpha

References

Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.Aldred, R. E. L.; McKay, B. D.; and Wormald, N. C. "Small Hypohamiltonian Graphs." J. Combin. Math. Combin. Comput. 23, 143-152, 1997.Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2011. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy, J. A. "Variations of the Hamiltonian Theme." Canad. Math. Bull. 15, 57-62, 1972.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 61, 1976.Chvátal, V. "Flip-Flops in Hypohamiltonian Graphs." Canad. Math. Bull. 16, 33-41, 1973.Collier, J. B. and Schmeichel, E. F. "Systematic Searches for Hypohamiltonian Graphs." Networks 8, 193-200, 1978.Doyen, J. and van Diest, V. "New Families of Hypohamiltonian Graphs." Disc. Math. 13, 225-236, 1975.Gaudin, T.; Herz, J.-C.; and Rossi, P. "Solution de problème no. 29." Française Informat. Recherche Opérationnelle 8, 214-218, 1964.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 66, 2001.Goedgebeur, J. and Zamfirescu, C. T. "Improved Bounds for Hypohamiltonian Graphs." Ars Math. Contemp. 13, 235-257, 2017.Grotschel, M. "On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations Res. 5, 285-292, 1980.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Hatzel, H. "Ein planarer hypohamiltonscher Graph mit 57 Knoten." Math Ann. 243, 213-216, 1979.Herz, J. C.; Duby, J. J.; and Vigué, F. "Recherche systématique des graphes hypohamiltoniens." In Theory of Graphs: Internat. Sympos., Rome 1966 (Ed. P. Rosenstiehl). Paris: Gordon and Breach, pp. 153-159, 1967.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.House of Graphs. "Hypohamiltonian Graphs." https://houseofgraphs.org/meta-directory/hypohamiltonian.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.Katerinis, P. "Some Properties of Hypohamiltonian Graphs." Aeq. Math. 72, 139-151, 2006.Lindgren, W. F. "An Infinite Class of Hypohamiltonian Graphs." Amer. Math. Monthly 74, 1087-1089, 1967.McKay, B. "Hypohamiltonian Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Skupień, Z. "Exponentially Many Hypohamiltonian Snarks." Electronic Notes in Disc. Meth. 28, 417-424, 2007.Sloane, N. J. A. Sequence A141150 in "The On-Line Encyclopedia of Integer Sequences."Sousselier, R. "Problème no. 29: Le cercle des irascibles." Rev. Franc. Rech. Operat. 7, 405-406, 1963.Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.Thomassen, C. "On Hypohamiltonian Graphs." Disc. Math. 10, 383-390, 1974.Thomassen, C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc. Math 14, 377-389, 1976.Thomassen, C. "Hypohamiltonian Graphs and Digraphs." In Theory and Applications of Graphs Proceedings, Michigan May 11-15, 1976 (Ed. Y. Alavi and D. R. Lick). New York: Springer-Verlag, pp. 557-571, 1978.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.Tsai, C.-C. "Small Planar Hypohamiltonian Graphs." 8 Apr 2024. https://arxiv.org/abs/2403.18384.Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th. 67, 55-68, 2011.Zamfirescu, C. T. and Zamfirescu, T. I. "A Planar Hypohamiltonian Graph with 48 Vertices." J. Graph Th. 48, 338-342, 2007.Zamfirescu, C. T. "Cubic Vertices in Planar Hypohamiltonian Graphs." J. Graph Th. 90, 189-207, 2019.

Referenced on Wolfram|Alpha

Hypohamiltonian Graph

Cite this as:

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

Subject classifications