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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 biconnected graph, then the square of G is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 19741.

Definitions and statement

An undirected graph G is Hamiltonian if it contains a cycle that touches each of its vertices exactly once. It is biconnected if it does not have an articulation vertex, a vertex whose deletion would leave the remaining graph disconnected. Not every biconnected graph is Hamiltonian; counterexamples include the Petersen graph and the complete bipartite graph K_{2,3} .

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 biconnected graph with at least three vertices must always be Hamiltonian. Equivalently, the vertices of every biconnected 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 biconnected, 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 biconnected 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 .

Primary sources

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

Secondary sources

. .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370011385 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Fleischner's theorem” revision 1370011385 · retrieved 2026-10-20 publication date (×2) · confidence 0.95 revision URL

Provenance

snapshot enwiki-001370011385 · captured 1787061738.0 · version history

Cite this page as: encyclopegia.org, “Fleischner's theorem”, snapshot enwiki-001370011385. https://encyclopegia.org/a/fleischner-s-theorem