Anundirected graph is Hamiltonian if it contains acycle that touches each of its vertices exactly once. It is 2-vertex-connected if it does not have an articulation vertex, a vertex whose deletion would leave the remaining graph disconnected. Not every 2-vertex-connected graph is Hamiltonian; counterexamples include thePetersen graph and thecomplete bipartite graph.
The square of is a graph that has the same vertex set as, and in which two vertices are adjacent if and only if they have distance at most two in. Fleischner's theorem states that the square of a finite 2-vertex-connected graph with at least three vertices must always be Hamiltonian. Equivalently, the vertices of every 2-vertex-connected graph may be arranged into acyclic order such that adjacent vertices in this order are at distance at most two from each other in.
In Fleischner's theorem, it is possible to constrain the Hamiltonian cycle in so that for given vertices and of it includes two edges of incident with and one edge of incidentwith. Moreover, if and are adjacent in, then these are three different edges of.[1]
In addition to having a Hamiltonian cycle, the square of a 2-vertex-connected graph must also be Hamiltonian connected (meaning that it has aHamiltonian path starting and ending at any two designated vertices) and 1-Hamiltonian (meaning that if any vertex is deleted, the remaining graph still has a Hamiltonian cycle).[2] It must also be vertexpancyclic, meaning that for every vertex and every integer with, there exists a cycle of length containing.[3]
If a graph is not 2-vertex-connected, then its square may or may not have a Hamiltonian cycle, and determining whether it does have one isNP-complete.[4]
An infinite graph cannot have a Hamiltonian cycle, because every cycle is finite, butCarsten Thomassen proved that if is an infinite locally finite 2-vertex-connected graph with a singleend then necessarily has a doubly infinite Hamiltonian path.[5] More generally, if is locally finite, 2-vertex-connected, and has any number of ends, then has a Hamiltonian circle. In acompact topological space formed by viewing the graph as asimplicial complex and adding an extra point at infinity to each of its ends, a Hamiltonian circle is defined to be a subspace that ishomeomorphic to a Euclidean circle and covers every vertex.[6]
A proof of Fleischner's theorem was announced byHerbert Fleischner in 1971 and published by him in 1974, solving a 1966 conjecture ofCrispin Nash-Williams also made independently byL. W. Beineke andMichael D. Plummer.[10] In his review of Fleischner's paper, Nash-Williams wrote that it had solved "a well known problem which has for several years defeated the ingenuity of other graph-theorists".[11]
Fleischner's original proof was complicated.Václav Chvátal, in the work in which he inventedgraph toughness, observed that the square of a-vertex-connected graph is necessarily-tough; heconjectured that 2-tough graphs are Hamiltonian, from which another proof of Fleischner's theorem would have followed.[12] Counterexamples to this conjecture were later discovered,[13] but the possibility that a finite bound on toughness might imply Hamiltonicity remains an important open problem in graph theory. A simpler proof both of Fleischner's theorem, and of its extensions byChartrand et al. (1974), was given byŘíha (1991),[14] and another simplified proof of the theorem was given byGeorgakopoulos (2009a).[15]
Alstrup, Stephen; Georgakopoulos, Agelos; Rotenberg, Eva;Thomassen, Carsten (2018), "A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time",Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1645–1649,doi:10.1137/1.9781611975031.107,ISBN978-1-61197-503-1
Bondy, J. A. (1971), "Pancyclic graphs",Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971), Baton Rouge, Louisiana: Louisiana State University, pp. 167–172,MR0325458.
Fleischner, H. (1976), "In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts",Monatshefte für Mathematik,82 (2):125–149,doi:10.1007/BF01305995,MR0427135.
Lau, H. T. (1980),Finding a Hamiltonian cycle in the square of a block., Ph.D. thesis, Montreal: McGill University. As cited byHochbaum & Shmoys (1986).
Parker, R. Garey; Rardin, Ronald L. (1984), "Guaranteed performance heuristics for the bottleneck traveling salesman problem",Operations Research Letters,2 (6):269–272,doi:10.1016/0167-6377(84)90077-4.
