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.

A 2-vertex-connected graph, its square, and a Hamiltonian cycle in the square

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 K2,3.

The square of G is a graph G2 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 constraint the Hamiltonian cycle in G2 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 with w. Moreover, if v and w are adjacent in G, then these are three different edges of G.[1]

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).[2] It must also be vertex pancyclic, meaning that for every vertex v and every integer k with 3 ≤ k ≤ |V(G)|, there exists a cycle of length k containing v.[3]

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.[4]

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 G2 necessarily has a doubly infinite Hamiltonian path.[5] More generally, if G is locally finite, 2-vertex-connected, and has any number of ends, then G2 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.[6]

Algorithms

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

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.[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 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.[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

Notes
  1. Fleischner (1976); Müttel & Rautenbach (2012).
  2. Chartrand et al. (1974); Chartrand, Lesniak & Zhang (2010)
  3. Hobbs (1976), answering a conjecture of Bondy (1971).
  4. Underground (1978); Bondy (1995).
  5. Thomassen (1978).
  6. Georgakopoulos (2009b); Diestel (2012).
  7. Alstrup, Georgakopoulos, Rotenberg, Thomassen (2018)
  8. Lau (1980); Parker & Rardin (1984).
  9. Parker & Rardin (1984); Hochbaum & Shmoys (1986).
  10. Fleischner (1974). For the earlier conjectures see Fleischner and Chartrand, Lesniak & Zhang (2010).
  11. MR0332573.
  12. Chvátal (1973); Bondy (1995).
  13. Bauer, Broersma & Veldman (2000).
  14. Bondy (1995); Chartrand, Lesniak & Zhang (2010).
  15. Chartrand, Lesniak & Zhang (2010); Diestel (2012).

Primary sources

Secondary sources
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.