Fleischner's Theorem

In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if $G$ is a 2-vertex-connected graph, then the square of $G$ is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 1974.

Definitions and statement

An undirected graph $G$ is Hamiltonian if it contains a cycle 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 the Petersen graph and the complete bipartite graph $K_$.

The square of $G$ is a graph $G^2$ that has the same vertex set as $G$, and in which two vertices are adjacent if and only if they have distance at most two in $G$. 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 $G$ may be arranged into a cyclic order such that adjacent vertices in this order are at distance at most two from each other in $G$.

Extensions

In Fleischner's theorem, it is possible to constrain the Hamiltonian cycle in $G^2$ so that for given vertices $v$ and $w$ of $G$ it includes two edges of $G$ incident with $v$ and one edge of $G$ incident Moreover, if $v$ and $w$ are adjacent in $G$, then these are three different edges of $G$.

In addition to having a Hamiltonian cycle, the square of a 2-vertex-connected graph $G$ must also be Hamiltonian connected (meaning that it has a Hamiltonian 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). It must also be vertex pancyclic, meaning that for every vertex $v$ and every integer $k$ with $3\le k\le, V(G)$, there exists a cycle of length $k$ containing $v$.

If a graph $G$ is not 2-vertex-connected, then its square may or may not have a Hamiltonian cycle, and determining whether it does have one is NP-complete.

An infinite graph cannot have a Hamiltonian cycle, because every cycle is finite, but Carsten Thomassen proved that if $G$ is an infinite locally finite 2-vertex-connected graph with a single end then $G^2$ necessarily has a doubly infinite Hamiltonian path. More generally, if $G$ is locally finite, 2-vertex-connected, and has any number of ends, then $G^2$ has a Hamiltonian circle. In a compact topological space formed by viewing the graph as a simplicial complex and adding an extra point at infinity to each of its ends, a Hamiltonian circle is defined to be a subspace that is homeomorphic to a Euclidean circle and covers every vertex.

Algorithms

The Hamiltonian cycle in the square of an $n$-vertex 2-connected graph can be found in linear time, improving over the first algorithmic solution by Lau of running time $O(n^2)$.
Fleischner's theorem can be used to provide a 2-approximation to the bottleneck traveling salesman problem in metric spaces.

History

A proof of Fleischner's theorem was announced by Herbert Fleischner in 1971 and published by him in 1974, solving a 1966 conjecture of Crispin Nash-Williams also made independently by L. W. Beineke and Michael D. Plummer. 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".

Fleischner's original proof was complicated. Václav Chvátal, in the work in which he invented graph toughness, observed that the square of a $k$-vertex-connected graph is necessarily $k$-tough; he conjectured that 2-tough graphs are Hamiltonian, from which another proof of Fleischner's theorem would have followed. Counterexamples to this conjecture were later discovered, 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 by , was given by , and another simplified proof of the theorem was given by .; .

References

Notes

Primary sources

*
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*. As cited by .
*.
*.
*.
*.
*.

Secondary sources

*.
*.
*{{citation
, last = Diestel , first = Reinhard
, contribution = 10. Hamiltonian cycles
, edition = corrected 4th electronic
, title = Graph Theory
, url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf
, year = 2012

Theorems in graph theory