- Hypohamiltonian graph
In the mathematical field of
graph theory , a graph "G" is said to be hypohamiltonian if "G" does not itself have aHamiltonian cycle but every graph formed by removing a single vertex from "G" is Hamiltonian.History
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.”
Applications
Hypohamiltonian graphs arise in
integer programming solutions to thetraveling salesman problem : certain kinds of hypohamiltonian graphs define facets of the "traveling salesman polytope", a shape defined as theconvex hull of the set of possible solutions to the traveling salesman problem, and these facets may be used incutting-plane method s for solving the problem. [harvtxt|Grötschel|1977; harvtxt|Grötschel|1980; harvtxt|Grötschel|Wakabayashi|1981.] harvtxt|Grötschel|1980 observes that thecomputational 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 .Properties
Every hypohamiltonian graph must be 3-vertex-connected, as the removal of any two vertices leaves a Hamiltonian path, which is connected. There exist "n"-vertex hypohamiltonian graphs in which the maximum degree is "n"/2, and in which there are approximately "n"2/4 edges. [harvtxt|Thomassen|1981.]
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 found planar hypohamiltonian graphs of girth 3, 4, and 5 and showed that there exist infinitely many planar hypohamiltonian graphs.] the smallest of which has 48 vertices. [harvtxt|Zamfirescu|Zamfirescu|2007. An earlier small planar hypohamiltonian graph with 57 vertices was found by harvtxt|Hatzel|1979.] 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 three-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 amatching and may be colored with a third color.The color classes of any 3-coloring of the edges of a 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 aninduced subgraph of some hypohamiltonian graph. [harvtxt|Collier|Schmeichel|1977.]Examples
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 5 (mod 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 classificiation 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
cubic graph s 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.
Enumeration
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 10-vertex Petersen graph, a 13-vertex graph and a 15-vertex graph found by computer searches of harvtxt|Herz|1968, and four 16-vertex graphs. There exist at least thirteen 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.]Generalizations
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 graph s 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.
Notes
References
*citation
first1 = R. A. | last1 = Aldred
first2 = B. D. | last2 = McKay | authorlink2 = Brendan McKay
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.
title = The classification of Hamiltonian generalized Petersen graphs
journal = Journal of Combinatorial Theory, Series B
volume = 34 | pages = 293–312 | year = 1983
id = MathSciNet | id = 0714452
doi = 10.1016/0095-8956(83)90042-4.*citation
last = Bondy | first = J. A.
title = Variations of the Hamiltonian theme
journal = Canadian Mathematical Bulletin
volume = 15 | pages = 57–62 | year = 1972.*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
id = MathSciNet | id = 0371722.*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 = ftp://reports.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
id = MathSciNet | id = 0543828
doi = 10.1016/0012-365X(77)90130-3.*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
id = MathSciNet | id = 0416979
doi = 10.1016/0012-365X(75)90020-5.*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
id = MathSciNet | id = 0498218.*citation
last1 = Gaudin | first1 = T. | last2 = Herz | first2 = J. C.
last3 = Rossi | first2 = P.
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.
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.*citation
last = Grötschel | first = M.
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.
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
url = http://www.jstor.org/stable/3689157.*citation
last1 = Grötschel | first1 = M. | last2 = Wakabayashi | first2 = Y.
title = Hypohamiltonian digraphs
journal = Mathematics of Operations Research
volume = 36 | year = 1980 | pages = 99–119.*citation
last1 = Grötschel | first1 = M. | last2 = Wakabayashi | first2 = Y.
title = On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets
journal = Discrete Mathematics
volume = 24 | year = 1981 | pages = 43–59.*citation
last1 = Grötschel | first1 = M. | last2 = Wakabayashi | first2 = Y.
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 A
volume = 17 | year = 1974 | pages = 31–38
id = MathSciNet | id = 0349474.*citation
last = Gutt | first = S.
title = Infinite families of hypohamiltonian graphs
journal = Académie Royale de Belgique, Bulletin de la Classe des Sciences, Koninklijke Belgische Academie, Mededelingen van de Klasse der Wetenschappen, 5e Série
volume = 63 | year = 1977 | issue = 5 | pages = 432–440
id = MathSciNet | id = 0498243.*citation
last = Häggkvist | first = R.
contribution = Problem 443. Special case of the Fulkerson Conjecture
editor1-last = Mohar | editor1-first = B.
editor2-last = Nowakowski | editor2-first = R. J.
editor3-last = West | editor3-first = D. B.
title = Research problems from the 5th Slovenian Conference (Bled, 2003)
journal = Discrete Mathematics
volume = 307 | issue = 3–5 | year = 2007 | pages = 650–658
doi = 10.1016/j.disc.2006.07.013.*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
id = MathSciNet | id = 0548801
doi = 10.1007/BF01424541.*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
id = MathSciNet | id = 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 = 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 | year = 1968 | pages = 195–201
id = MathSciNet | id = 0229543.*citation
last = Kronk | first = H. V.
contribution = Does there exist a hypotraceable graph?
editor-last = Klee | editor-first = V. | editor-link = Victor Klee
title = Research Problems
journal =American Mathematical Monthly
volume = 76 | issue = 7 | year = 1969 | pages = 809–810
url = http://www.jstor.org/stable/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
id = MathSciNet | id = 0224501
doi = 10.2307/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
url = http://www.combinatorics.org/Volume_14/Abstracts/v14i1r18.html.*citation
last1 = Menke | first1 = B.
last2 = Zamfirescu | first2 = T. I. | last3 = Zamfirescu | first3 = C. T.
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.*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.*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
id = MathSciNet | id = 2359901.*citation
last = Skupień | first = Z.
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
journal = 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.
contribution = Problème no. 29: Le cercle des irascibles
editor-last = Berge | editor-first = C. | editor-link = Claude Berge
title = Problèmes plaisants et delectables
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
id = MathSciNet | id = 1630478
doi = 10.1016/S0012-365X(97)00255-0.*citation
last = Steffen | first = E.
title = On bicritical snarks
journal = Math. Slovaca
volume = 51 | year = 2001 | issue = 2 | pages = 141–150
id = MathSciNet | id = 1841443.*citation
last = Thomassen | first = Carsten | authorlink = Carsten Thomassen
title = Hypohamiltonian and hypotraceable graphs
journal = Discrete Mathematics
volume = 9 | year = 1974a | pages = 91–96
id = MathSciNet | id = 0347682
doi = 10.1016/0012-365X(74)90074-0.*citation
last = Thomassen | first = Carsten | authorlink = Carsten Thomassen
title = On hypohamiltonian graphs
journal = Discrete Mathematics
volume = 10 | year = 1974b | pages = 383–390
id = MathSciNet | id = 0357226
doi = 10.1016/0012-365X(74)90128-9.*citation
last = Thomassen | first = Carsten | authorlink = Carsten Thomassen
title = Planar and infinite hypohamiltonian and hypotraceable graphs
journal = Discrete Mathematics
volume = 14 | year = 1976 | pages = 377–389
id = MathSciNet | id = 0422086
doi = 10.1016/0012-365X(76)90071-6.*citation
last = Thomassen | first = Carsten | authorlink = Carsten Thomassen
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
id = MathSciNet | id = 0499523.*citation
last = Thomassen | first = Carsten | authorlink = Carsten Thomassen
title = Planar cubic hypo-Hamiltonian and hypotraceable graphs
journal = Journal of Combinatorial Theory, Series B
volume = 30 | year = 1981 | pages = 36–44
id = MathSciNet | id = 0609592
doi = 10.1016/0095-8956(81)90089-7.*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.External links
*
Wikimedia Foundation. 2010.