Hypohamiltonian graph

Hypohamiltonian graphs were first studied by {{harvtxt|Sousselier|1963}}. {{harvtxt|Lindgren|1967}} cites {{harvtxt|Gaudin|Herz|Rossi|1964}} and {{harvtxt|Busacker|Saaty|1965}} as additional early papers on the subject; another early work is by {{harvtxt|Herz|Duby|Vigué|1967}}.

{{harvtxt|Grötschel|1980}} sums up much of the research in this area with the following sentence: “The articles dealing with those graphs ... usually exhibit new classes of hypohamiltonian or hypotraceable graphs showing that for certain orders n such graphs indeed exist or that they possess strange and unexpected properties.”

Hypohamiltonian graphs arise in integer programming solutions to the traveling salesman problem: certain kinds of hypohamiltonian graphs define facets of the traveling salesman polytope, a shape defined as the convex hull of the set of possible solutions to the traveling salesman problem, and these facets may be used in cutting-plane methods for solving the problem.{{harvtxt|Grötschel|1977}}; {{harvtxt|Grötschel|1980}}; {{harvtxt|Grötschel|Wakabayashi|1981}}. {{harvtxt|Grötschel|1980}} observes that the computational complexity of determining whether a graph is hypohamiltonian, although unknown, is likely to be high, making it difficult to find facets of these types except for those defined by small hypohamiltonian graphs; fortunately, the smallest graphs lead to the strongest inequalities for this application.{{harvtxt|Goemans|1995}}.

Concepts closely related to hypohamiltonicity have also been used by {{harvtxt|Park|Lim|Kim|2007}} to measure the fault tolerance of network topologies for parallel computing.

Every hypohamiltonian graph must be 3-vertex-connected, as the removal of any two vertices leaves a Hamiltonian path, which is connected. There exist {{nowrap|n-vertex}} hypohamiltonian graphs in which the maximum degree is n/2, and in which there are approximately n²/4 edges.{{harvtxt|Thomassen|1981}}.

File:Thomassen girth-3 hypohamiltonian.svg

{{harvtxt|Herz|Duby|Vigué|1967}} conjectured that every hypohamiltonian graph has girth 5 or more, but this was disproved by {{harvtxt|Thomassen|1974b}}, who found examples with girth 3 and 4. For some time it was unknown whether a hypohamiltonian graph could be planar, but several examples are now known,The existence of planar hypohamiltonian graphs was posed as an open question by {{harvtxt|Chvátal|1973}}, and {{harvtxt|Chvátal|Klarner|Knuth|1972}} offered a $5 prize for the construction of one. {{harvtxt|Thomassen|1976}} used Grinberg's theorem to find planar hypohamiltonian graphs of girth 3, 4, and 5 and showed that there exist infinitely many planar hypohamiltonian graphs. the smallest of which has 40 vertices.{{harvtxt|Jooyandeh|McKay|Östergård|Pettersson|2017}}, using a computer search and Grinberg's theorem. Earlier small planar hypohamiltonian graphs with 42, 57 and 48 vertices, respectively, were found by {{harvtxt|Wiener|Araya|2009}}, {{harvtxt|Hatzel|1979}} and {{harvtxt|Zamfirescu|Zamfirescu|2007}}. Every planar hypohamiltonian graph has at least one vertex with only three incident edges.{{harvtxt|Thomassen|1978}}.

If a 3-regular graph is Hamiltonian, its edges can be colored with three colors: use alternating colors for the edges on the Hamiltonian cycle (which must have even length by the handshaking lemma) and a third color for all remaining edges. Therefore, all snarks, bridgeless cubic graphs that require four edge colors, must be non-Hamiltonian, and many known snarks are hypohamiltonian. Every hypohamiltonian snark is bicritical: removing any two vertices leaves a subgraph the edges of which can be colored with only three colors.{{harvtxt|Steffen|1998}}; {{harvtxt|Steffen|2001}}. A {{nowrap|3-coloring}} of this subgraph can be simply described: after removing one vertex, the remaining vertices contain a Hamiltonian cycle. After removing a second vertex, this cycle becomes a path, the edges of which may be colored by alternating between two colors. The remaining edges form a matching and may be colored with a third color.

The color classes of any 3-coloring of the edges of a {{nowrap|3-regular}} graph form three matchings such that each edge belongs to exactly one of the matchings.

Hypohamiltonian snarks do not have a partition into matchings of this type, but {{harvtxt|Häggkvist|2007}} conjectures that the edges of any hypohamiltonian snark may be used to form six matchings such that each edge belongs to exactly two of the matchings. This is a special case of the Berge–Fulkerson conjecture that any snark has six matchings with this property.

Hypohamiltonian graphs cannot be bipartite: in a bipartite graph, a vertex can only be deleted to form a Hamiltonian subgraph if it belongs to the larger of the graph's two color classes. However, every bipartite graph occurs as an induced subgraph of some hypohamiltonian graph.{{harvtxt|Collier|Schmeichel|1977}}.

The smallest hypohamiltonian graph is the Petersen graph {{harv|Herz|Duby|Vigué|1967}}. More generally, the generalized Petersen graph GP(n,2) is hypohamiltonian when n is congruent to 5 modulo 6;{{harvtxt|Robertson|1969}} proved that these graphs are non-Hamiltonian, while it is straightforward to verify that their one-vertex deletions are Hamiltonian. See {{harvtxt|Alspach|1983}} for a classification of non-Hamiltonian generalized Petersen graphs. the Petersen graph is the instance of this construction with n = 5.

{{harvtxt|Lindgren|1967}} found another infinite class of hypohamiltonian graphs in which the number of vertices is 4 mod 6. Lindgren's construction consists of a cycle of length 3 mod 6 and a single central vertex; the central vertex is connected to every third vertex of the cycle by edges he calls spokes, and the vertices two positions away from each spoke endpoint are connected to each other. Again, the smallest instance of Lindgren's construction is the Petersen graph.

Additional infinite families are given by {{harvtxt|Bondy|1972}}, {{harvtxt|Doyen|van Diest|1975}}, and {{harvtxt|Gutt|1977}}.

Václav Chvátal proved in 1973 that for all sufficiently large n there exists a hypohamiltonian graph with n vertices. Taking into account subsequent discoveries,{{harvtxt|Thomassen|1974a}}; {{harvtxt|Doyen|van Diest|1975}}. “sufficiently large” is now known to mean that such graphs exist for all n ≥ 18. A complete list of hypohamiltonian graphs with at most 17 vertices is known:{{harvtxt|Aldred|McKay|Wormald|1997}}. See also {{OEIS|id=A141150}}. they are the {{nowrap|10-vertex}} Petersen graph, a {{nowrap|13-vertex}} graph and a {{nowrap|15-vertex}} graph found by computer searches of {{harvtxt|Herz|1968}}, and four {{nowrap|16-vertex}} graphs. There exist at least thirteen {{nowrap|18-vertex}} hypohamiltonian graphs. By applying the flip-flop method of {{harvtxt|Chvátal|1973}} to the Petersen graph and the flower snark, it is possible to show that the number of hypohamiltonian graphs, and more specifically the number of hypohamiltonian snarks, grows as an exponential function of the number of vertices.{{harvtxt|Skupień|1989}}; {{harvtxt|Skupień|2007}}.

Graph theorists have also studied hypotraceable graphs, graphs that do not contain a Hamiltonian path but such that every subset of n − 1 vertices may be connected by a path.{{harvtxt|Kapoor|Kronk|Lick|1968}}; {{harvtxt|Kronk|1969}}; {{harvtxt|Grünbaum|1974}}; {{harvtxt|Thomassen|1974a}}. Analogous definitions of hypohamiltonicity and hypotraceability for directed graphs have been considered by several authors.{{harvtxt|Fouquet|Jolivet|1978}}; {{harvtxt|Grötschel|Wakabayashi|1980}}; {{harvtxt|Grötschel|Wakabayashi|1984}}; {{harvtxt|Thomassen|1978}}.

An equivalent definition of hypohamiltonian graphs is that their longest cycle has length n − 1 and that the intersection of all longest cycles is empty. {{harvtxt|Menke|Zamfirescu|Zamfirescu|1998}} investigate graphs with the same property that the intersection of longest cycles is empty but in which the longest cycle length is shorter than n − 1. {{harvtxt|Herz|1968}} defines the cyclability of a graph as the largest number k such that every k vertices belong to a cycle; the hypohamiltonian graphs are exactly the graphs that have cyclability n − 1. Similarly, {{harvtxt|Park|Lim|Kim|2007}} define a graph to be ƒ-fault hamiltonian if the removal of at most ƒ vertices leaves a Hamiltonian subgraph. {{harvtxt|Schauerte|Zamfirescu|2006}} study the graphs with cyclability n − 2.

{{reflist|2}}

{{refbegin|30em}}

• {{citation

| first1 = R. A. | last1 = Aldred

| first2 = B. D. | last2 = McKay | authorlink2 = Brendan McKay (mathematician)

| first3 = N. C. | last3 = Wormald

| title = Small hypohamiltonian graphs

| journal = J. Combinatorial Math. Combinatorial Comput.

| volume = 23 | year = 1997 | pages = 143–152

| url = http://cs.anu.edu.au/people/bdm/papers/hypo.pdf}}.

• {{citation

| last1 = Alspach | first1 = B. R. | authorlink = Brian Alspach

| title = The classification of Hamiltonian generalized Petersen graphs

| journal = Journal of Combinatorial Theory | series=Series B

| volume = 34 | pages = 293–312 | year = 1983

|mr=0714452

| doi = 10.1016/0095-8956(83)90042-4

| issue = 3| doi-access = free

}}.

• {{citation

| last = Bondy | first = J. A.

| title = Variations of the Hamiltonian theme

| journal = Canadian Mathematical Bulletin

| volume = 15 | pages = 57–62 | year = 1972

| doi = 10.4153/CMB-1972-012-3 | doi-access =free }}.

• {{citation

| last1 = Busacker | first1 = R. G. | last2 = Saaty | first2 = T. L.

| title = Finite Graphs and Networks

| publisher = McGraw-Hill | year = 1965}}.

• {{citation

| authorlink = Václav Chvátal | first = V. | last = Chvátal

| title = Flip-flops in hypo-Hamiltonian graphs

| journal = Canadian Mathematical Bulletin

| volume = 16 | year = 1973 | pages = 33–41

| mr=0371722

| doi = 10.4153/CMB-1973-008-9 | doi-access = free}}.

• {{citation

|authorlink1=Václav Chvátal

|first1=V.

|last1=Chvátal

|first2=D. A.

|last2=Klarner

|first3=D. E.

|last3=Knuth

|authorlink3=Donald Knuth

|title=Selected Combinatorial Research Problems

|series=Tech. Report STAN-CS-72-292

|publisher=Computer Science Department, Stanford University

|year=1972

|url=http://i.stanford.edu/pub/cstr/reports/cs/tr/72/292/CS-TR-72-292.pdf}}.

• {{citation

| last1 = Collier | first1 = J. B. | last2 = Schmeichel | first2 = E. F.

| title = New flip-flop constructions for hypohamiltonian graphs

| journal = Discrete Mathematics

| volume = 18 | year = 1977 | issue = 3 | pages = 265–271

|mr=0543828

| doi = 10.1016/0012-365X(77)90130-3| doi-access = }}.

• {{citation

| last1 = Doyen | first1 = J.

| last2 = van Diest | first2 = V.

| title = New families of hypohamiltonian graphs

| journal = Discrete Mathematics

| volume = 13 | pages = 225–236 | year = 1975

|mr=0416979

| doi = 10.1016/0012-365X(75)90020-5

| issue = 3| doi-access = free

}}.

• {{citation

| last1 = Fouquet | first1 = J.-L. | last2 = Jolivet | first2 = J. L.

| title = Hypohamiltonian oriented graphs

| journal = Cahiers Centre Études Rech. Opér.

| volume = 20 | year = 1978 | issue = 2 | pages = 171–181

|mr=0498218}}.

• {{citation

| last1 = Gaudin | first1 = T. | last2 = Herz | first2 = P.

| last3 = Rossi

| title = Solution du problème No. 29

| journal = Rev. Franç. Rech. Opérationnelle

| volume = 8 | year = 1964 | pages = 214–218}}.

• {{citation

| last = Goemans | first = Michel X. | authorlink=Michel Goemans

| title = Worst-case comparison of valid inequalities for the TSP

| journal = Mathematical Programming

| volume = 69 | year = 1995 | issue = 1–3 | pages = 335–349

| doi = 10.1007/BF01585563| citeseerx = 10.1.1.52.8008

| s2cid = 214113

}}.

• {{citation

| last = Grötschel | first = M. | authorlink = Martin Grötschel

| title = Hypohamiltonian facets of the symmetric travelling salesman polytope

| journal = Zeitschrift für Angewandte Mathematik und Mechanik

| volume = 58 | year = 1977 | pages = 469–471}}.

• {{citation

| last = Grötschel | first = M. | authorlink = Martin Grötschel

| title = On the monotone symmetric traveling salesman problem: hypohamiltonian/hypotraceable graphs and facets

| journal = Mathematics of Operations Research

| volume = 5 | pages = 285–292 | year = 1980

| doi = 10.1287/moor.5.2.285

| jstor = 3689157

| issue = 2}}.

• {{citation

| last1 = Grötschel | first1 = M. | author1-link = Martin Grötschel | last2 = Wakabayashi | first2 = Y. | author2-link = Yoshiko Wakabayashi

| title = Hypohamiltonian digraphs

| journal = Methods of Operations Research

| volume = 36 | year = 1980 | pages = 99–119

| zbl = 0436.05038}}.

• {{citation

| last1 = Grötschel | first1 = M. | author1-link = Martin Grötschel | last2 = Wakabayashi | first2 = Y. | author2-link = Yoshiko Wakabayashi

| title = On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

| journal = Discrete Mathematics

| volume = 24 | year = 1981 | pages = 43–59

| doi = 10.1016/0012-365X(81)90021-2| doi-access = free }}.

• {{citation

| last1 = Grötschel | first1 = M. | author1-link = Martin Grötschel | last2 = Wakabayashi | first2 = Y. | author2-link = Yoshiko Wakabayashi

| contribution = Constructions of hypotraceable digraphs

| editor1-first = R. W. | editor1-last = Cottle

| editor2-first = M. L. | editor2-last = Kelmanson

| editor3-first = B. | editor3-last = Korte

| title = Mathematical Programming (Proc. International Congress, Rio de Janeiro, 1981)

| publisher = North-Holland | year = 1984}}.

• {{citation

| last = Grünbaum | first = B. | authorlink = Branko Grünbaum

| title = Vertices missed by longest paths or circuits

| journal = Journal of Combinatorial Theory | series=Series A

| volume = 17 | year = 1974 | pages = 31–38

| mr=0349474

| doi = 10.1016/0097-3165(74)90025-9| doi-access = free}}.

• {{citation

| last = Gutt | first = Simone | authorlink = Simone Gutt

| title = Infinite families of hypohamiltonian graphs

| journal = Académie Royale de Belgique, Bulletin de la Classe des Sciences

| series=5e Série

| volume = 63 | year = 1977 | issue = 5 | pages = 432–440

|mr=0498243}}.

• {{citation|last=Häggkvist|first= R.|year=2007|title=Problem 443. Special case of the Fulkerson Conjecture|editor1-link=Bojan Mohar|editor1-last=Mohar|editor1-first=B.|editor2-last=Nowakowski|editor2-first=R. J.|editor3-last=West|editor3-first=D. B.|department=Research problems from the 5th Slovenian Conference (Bled, 2003)|journal=Discrete Mathematics|volume=307|issue=3–5|pages=650–658|doi=10.1016/j.disc.2006.07.013|doi-access=}}.
• {{citation

| last1 = Hatzel | first1 = W.

| title = Ein planarer hypohamiltonscher Graph mit 57 Knoten

| journal = Math. Ann.

| volume = 243 | year = 1979 | issue = 3 | pages = 213–216

|mr=0548801

| doi = 10.1007/BF01424541| s2cid = 121794449

}}.

• {{citation

| last1 = Herz | first1 = J. C.

| contribution = Sur la cyclabilité des graphes

| title = Computers in Mathematical Research

| publisher = North-Holland | year = 1968 | pages = 97–107

|mr=0245461}}.

• {{citation

| last1 = Herz | first1 = J. C.

| last2 = Duby | first2 = J. J.

| last3 = Vigué | first3 = F.

| contribution = Recherche systématique des graphes hypohamiltoniens

| title = Theory of Graphs: International Symposium, Rome 1966

| editor-first = P. | editor-last = Rosenstiehl | editor-link = Pierre Rosenstiehl

| location = Paris | publisher = Gordon and Breach | pages = 153–159 | year = 1967}}.

• {{citation

| last1 = Jooyandeh | first1 = Mohammadreza

| last2 = McKay | first2 = Brendan D. | authorlink2 = Brendan McKay (mathematician)

| last3 = Östergård | first3 = Patric R. J.

| last4 = Pettersson | first4 = Ville H.

| last5 = Zamfirescu | first5 = Carol T.

| title = Planar Hypohamiltonian Graphs on 40 Vertices

| year = 2017

| arxiv = 1302.2698

| bibcode = 2013arXiv1302.2698J

| journal = Journal of Graph Theory

| volume=84

| issue=2

| pages=121–133

| doi=10.1002/jgt.22015}}.

• {{citation

| last1 = Kapoor | first1 = S. F. | last2 = Kronk | first2 = H. V.

| last3 = Lick | first3 = D. R.

| title = On detours in graphs

| journal = Canadian Mathematical Bulletin

| volume = 11 | issue = 2 | year = 1968 | pages = 195–201

|mr=0229543

| doi = 10.4153/CMB-1968-022-8 | doi-access=free }}.

• {{citation

| last = Kronk | first = H. V.

| title = Does there exist a hypotraceable graph?

| editor-last = Klee | editor-first = V. | editor-link = Victor Klee

| department = Research Problems

| journal = American Mathematical Monthly

| volume = 76 | issue = 7 | year = 1969 | pages = 809–810

| jstor = 2317879 | doi=10.2307/2317879}}.

• {{citation

| last = Lindgren | first = W. F.

| title = An infinite class of hypohamiltonian graphs

| journal = American Mathematical Monthly

| volume = 74 | year = 1967 | pages = 1087–1089

|mr=0224501

| doi = 10.2307/2313617

| issue = 9

| jstor = 2313617}}.

• {{citation

| last1 = Máčajová | first1 = E.

| last2 = Škoviera | first2 = M.

| title = Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6

| journal = Electronic Journal of Combinatorics

| volume = 14 | issue = 1 | pages = R14 | year = 2007

| doi = 10.37236/936

| url = http://www.combinatorics.org/Volume_14/Abstracts/v14i1r18.html| doi-access = free}}.

• {{citation

| last1 = Menke | first1 = B.

| last2 = Zamfirescu | first2 = T. I. | last3 = Zamfirescu | first3 = C. M.

| title = Intersections of longest cycles in grid graphs

| journal = Journal of Graph Theory

| volume = 25 | issue = 1 | year = 1998 | pages = 37–52

| doi = 10.1002/(SICI)1097-0118(199705)25:1<37::AID-JGT2>3.0.CO;2-J}}.

• {{citation

| last1 = Mohanty | first1 = S. P. | last2 = Rao | first2 = D.

| contribution = A family of hypo-hamiltonian generalized prisms

| title = Combinatorics and Graph Theory

| series = Lecture Notes in Mathematics

| publisher = Springer-Verlag

| volume = 885 | year = 1981 | pages = 331–338 | doi = 10.1007/BFb0092278| isbn = 978-3-540-11151-1 }}.

• {{citation

| last1 = Park | first1 = J.-H. | last2 = Lim | first2 = H.-S. | last3 = Kim | first3 = H.-C.

| title = Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements

| journal = Theoretical Computer Science

| volume = 377 | issue = 1–3 | year = 2007 | pages = 170–180

| doi = 10.1016/j.tcs.2007.02.029| doi-access = }}.

• {{citation

| last = Robertson | first = G. N.

| title = Graphs minimal under girth, valency and connectivity constraints

| series = Ph. D. thesis

| publisher = University of Waterloo

| location = Waterloo, Ontario

| year = 1969}}.

• {{citation

| last1 = Schauerte | first1 = Boris | last2 = Zamfirescu | first2 = C. T.

| title = Regular graphs in which every pair of points is missed by some longest cycle

| journal = An. Univ. Craiova Ser. Mat. Inform.

| volume = 33 | year = 2006 | pages = 154–173

|mr=2359901| hdl = 1854/LU-6901462| hdl-access = free}}.

• {{citation

| last = Skupień | first = Z. |authorlink=Zdzislaw Skupien

| contribution = Exponentially many hypohamiltonian graphs

| title = Graphs, Hypergraphs and Matroids III (Proc. Conf. Kalsk 1988)

| publisher = Higher College of Engineering | location = Zielona Góra

| year = 1989 | pages = 123–132}}. As cited by {{harvtxt|Skupień|2007}}.

• {{citation

| last = Skupień | first = Z.

| contribution = Exponentially many hypohamiltonian snarks

| title = 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications

| series = Electronic Notes in Discrete Mathematics

| volume = 28 | year = 2007 | pages = 417–424

| doi = 10.1016/j.endm.2007.01.059}}.

• {{citation

| last = Sousselier | first = R.

| title = Problème no. 29: Le cercle des irascibles

| editor-last = Berge | editor-first = C. | editor-link = Claude Berge

| department = Problèmes plaisants et délectables

| journal = Rev. Franç. Rech. Opérationnelle

| volume = 7 | pages = 405–406 | year = 1963}}.

• {{citation

| last = Steffen | first = E.

| title = Classification and characterizations of snarks

| journal = Discrete Mathematics

| volume = 188 | year = 1998 | issue = 1–3 | pages = 183–203

|mr=1630478

| doi = 10.1016/S0012-365X(97)00255-0| doi-access = free}}.

• {{citation

| last = Steffen | first = E.

| title = On bicritical snarks

| journal = Math. Slovaca

| volume = 51 | year = 2001 | issue = 2 | pages = 141–150

|mr=1841443}}.

• {{citation

| last = Thomassen | first = Carsten | authorlink = Carsten Thomassen (mathematician)

| title = Hypohamiltonian and hypotraceable graphs

| journal = Discrete Mathematics

| volume = 9 | year = 1974a | pages = 91–96

|mr=0347682

| doi = 10.1016/0012-365X(74)90074-0| doi-access = }}.

• {{citation

| last = Thomassen | first = Carsten | authorlink = Carsten Thomassen (mathematician)

| title = On hypohamiltonian graphs

| journal = Discrete Mathematics

| volume = 10 | year = 1974b | pages = 383–390

|mr=0357226

| doi = 10.1016/0012-365X(74)90128-9

| issue = 2| doi-access = free

}}.

• {{citation

| last = Thomassen | first = Carsten | authorlink = Carsten Thomassen (mathematician)

| title = Planar and infinite hypohamiltonian and hypotraceable graphs

| journal = Discrete Mathematics

| volume = 14 | year = 1976 | pages = 377–389

|mr=0422086

| doi = 10.1016/0012-365X(76)90071-6

| issue = 4| doi-access =

}}.

• {{citation

| last = Thomassen | first = Carsten | authorlink = Carsten Thomassen (mathematician)

| contribution = Hypohamiltonian graphs and digraphs

| title = Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976)

| pages = 557–571 | year = 1978 | volume = 642

| series = Lecture Notes in Mathematics

| publisher = Springer-Verlag | location = Berlin

|mr=0499523}}.

• {{citation

| last = Thomassen | first = Carsten | authorlink = Carsten Thomassen (mathematician)

| title = Planar cubic hypo-Hamiltonian and hypotraceable graphs

| journal = Journal of Combinatorial Theory | series=Series B

| volume = 30 | year = 1981 | pages = 36–44

|mr=0609592

| doi = 10.1016/0095-8956(81)90089-7| doi-access = free}}.

• {{citation

| last1 = Wiener | first1 = Gábor

| last2 = Araya | first2 = Makoto

| title = The ultimate question

| year = 2009

| arxiv = 0904.3012| bibcode = 2009arXiv0904.3012W}}.

• {{citation

| last1 = Zamfirescu | first1 = C. T. | last2 = Zamfirescu | first2 = T. I.

| title = A planar hypohamiltonian graph with 48 vertices

| journal = Journal of Graph Theory

| volume = 55 | year = 2007 | issue = 4 | pages = 338–342

| doi = 10.1002/jgt.20241}}.

{{refend}}

• {{mathworld|title=Hypohamiltonian Graph|urlname=HypohamiltonianGraph|mode=cs2}}

Category:Graph families

Category:Hamiltonian paths and cycles