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 {\displaystyle G} is a 2-vertex-connected graph, then the square of G {\displaystyle G} is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 1974.^[1]

Definitions and statement

An undirected graph G {\displaystyle 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 2 , 3 {\displaystyle K_{2,3}} .

The square of G {\displaystyle G} is a graph G 2 {\displaystyle G^{2}} that has the same vertex set as G {\displaystyle G} , and in which two vertices are adjacent if and only if they have distance at most two in G {\displaystyle 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 {\displaystyle 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 {\displaystyle G} .

Extensions

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

In addition to having a Hamiltonian cycle, the square of a 2-vertex-connected graph G {\displaystyle 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).^[3] It must also be vertex pancyclic, meaning that for every vertex v {\displaystyle v} and every integer k {\displaystyle k} with 3 ≤ k ≤ | V ( G ) {\displaystyle 3\leq k\leq |V(G)} , there exists a cycle of length k {\displaystyle k} containing v {\displaystyle v} .^[4]

If a graph G {\displaystyle 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.^[5]

An infinite graph cannot have a Hamiltonian cycle, because every cycle is finite, but Carsten Thomassen proved that if G {\displaystyle G} is an infinite locally finite 2-vertex-connected graph with a single end then G 2 {\displaystyle G^{2}} necessarily has a doubly infinite Hamiltonian path.^[6] More generally, if G {\displaystyle G} is locally finite, 2-vertex-connected, and has any number of ends, then G 2 {\displaystyle 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.^[7]

Algorithms

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

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.^[11] 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".^[1]

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 {\displaystyle k} -vertex-connected graph is necessarily k {\displaystyle k} -tough; he conjectured 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 by Chartrand et al. (1974), was given by Říha (1991),^[14] and another simplified proof of the theorem was given by Georgakopoulos (2009a).^[15]

References