Fleischner's theorem

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\_\{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 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$.

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 {{nowrap|with $w$.}} Moreover, if $v$ and $w$ are adjacent in $G$, then these are three different edges of $G$.{{harvtxt|Fleischner|1976}}; {{harvtxt|Müttel|Rautenbach|2012}}.

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).{{harvtxt|Chartrand|Hobbs|Jung|Kapoor|1974}}; {{harvtxt|Chartrand|Lesniak|Zhang|2010}} It must also be vertex pancyclic, meaning that for every vertex $v$ and every integer $k$ with $3\backslash le\; k\backslash le|V(G)$, there exists a cycle of length $k$ containing $v$.{{harvtxt|Hobbs|1976}}, answering a conjecture of {{harvtxt|Bondy|1971}}.

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.{{harvtxt|Underground|1978}}; {{harvtxt|Bondy|1995}}.

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.{{sfnp|Thomassen|1978}} 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.{{harvtxt|Georgakopoulos|2009b}}; {{harvtxt|Diestel|2012}}.

The Hamiltonian cycle in the square of an $n$-vertex 2-connected graph can be found in linear time,{{harvtxt|Alstrup|Georgakopoulos|Rotenberg|Thomassen|2018}} improving over the first algorithmic solution by Lau{{harvtxt|Lau|1980}}; {{harvtxt|Parker|Rardin|1984}}. 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.{{harvtxt|Parker|Rardin|1984}}; {{harvtxt|Hochbaum|Shmoys|1986}}.

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.{{harvtxt|Fleischner|1974}}. For the earlier conjectures see Fleischner and {{harvtxt|Chartrand|Lesniak|Zhang|2010}}. 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".{{MR|0332573}}.

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.{{harvtxt|Chvátal|1973}}; {{harvtxt|Bondy|1995}}. Counterexamples to this conjecture were later discovered,{{sfnp|Bauer|Broersma|Veldman|2000}} 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 {{harvtxt|Chartrand|Hobbs|Jung|Kapoor|1974}}, was given by {{harvtxt|Říha|1991}},{{harvtxt|Bondy|1995}}; {{harvtxt|Chartrand|Lesniak|Zhang|2010}}. and another simplified proof of the theorem was given by {{harvtxt|Georgakopoulos|2009a}}.{{harvtxt|Chartrand|Lesniak|Zhang|2010}}; {{harvtxt|Diestel|2012}}.

{{reflist|colwidth=30em}}

• {{citation

| last1 = Alstrup | first1 = Stephen | last2 = Georgakopoulos | first2 = Agelos

| last3 = Rotenberg | first3 = Eva | last4 = Thomassen | first4 = Carsten | author4-link = Carsten Thomassen (mathematician)

| title = Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | chapter = A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time

| doi = 10.1137/1.9781611975031.107

| year = 2018| pages = 1645–1649 | isbn = 978-1-61197-503-1 | doi-access = free }}

• {{citation

| last1 = Bauer | first1 = D.

| last2 = Broersma | first2 = H. J.

| last3 = Veldman | first3 = H. J.

| title = Not every 2-tough graph is Hamiltonian

| doi = 10.1016/S0166-218X(99)00141-9

| issue = 1–3

| journal = Discrete Applied Mathematics

| mr = 1743840

| pages = 317–321

| department = Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997)

| volume = 99

| year = 2000| url = https://research.utwente.nl/en/publications/not-every-2tough-graph-is-hamiltonian(8189db8b-1470-4c06-b5a2-19d621bfc91b).html

| doi-access = free

}}.

• {{citation

| last = Bondy | first = J. A. | author-link = John Adrian Bondy

| contribution = Pancyclic graphs

| location = Baton Rouge, Louisiana

| mr = 0325458

| pages = 167–172

| publisher = Louisiana State University

| title = Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971)

| year = 1971}}.

• {{citation

| last1 = Chartrand | first1 = G. | author1-link = Gary Chartrand

| last2 = Hobbs | first2 = Arthur M. | author2-link = Arthur Hobbs (mathematician)

| last3 = Jung | first3 = H. A.

| last4 = Kapoor | first4 = S. F.

| last5 = Nash-Williams | first5 = C. St. J. A. | author5-link = Crispin Nash-Williams

| doi = 10.1016/0095-8956(74)90075-6

| journal = Journal of Combinatorial Theory

| mr = 0345865

| pages = 290–292

| series = Series B

| title = The square of a block is Hamiltonian connected

| volume = 16

| year = 1974| issue = 3 | doi-access = free

}}.

• {{citation

| last = Chvátal | first = Václav | author-link = Václav Chvátal

| doi = 10.1016/0012-365X(73)90138-6

| issue = 3

| journal = Discrete Mathematics

| pages = 215–228

| title = Tough graphs and Hamiltonian circuits

| volume = 5

| year = 1973

| mr = 0316301| doi-access = free

}}.

• {{citation

| last = Fleischner | first = Herbert

| doi = 10.1016/0095-8956(74)90091-4

| journal = Journal of Combinatorial Theory

| mr = 0332573

| pages = 29–34

| series = Series B

| title = The square of every two-connected graph is Hamiltonian

| volume = 16

| year = 1974| doi-access = free

}}.

• {{citation

| last = Fleischner | first = H.

| doi = 10.1007/BF01305995

| issue = 2

| journal = Monatshefte für Mathematik

| mr = 0427135

| pages = 125–149

| title = In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts

| volume = 82

| year = 1976}}.

• {{citation

| last = Georgakopoulos | first = Agelos

| doi = 10.1016/j.disc.2009.06.024 | doi-access=free

| issue = 23–24

| journal = Discrete Mathematics

| mr = 2558627

| pages = 6632–6634

| title = A short proof of Fleischner's theorem

| volume = 309

| year = 2009a}}.

• {{citation

| last = Georgakopoulos | first = Agelos

| doi = 10.1016/j.aim.2008.09.014 | doi-access=free

| issue = 3

| journal = Advances in Mathematics

| mr = 2483226

| pages = 670–705

| title = Infinite Hamilton cycles in squares of locally finite graphs

| volume = 220

| year = 2009b}}.

• {{citation

| last = Hobbs | first = Arthur M.

| doi = 10.1016/0095-8956(76)90061-7

| issue = 1

| journal = Journal of Combinatorial Theory

| mr = 0416980

| pages = 1–4

| series = Series B

| title = The square of a block is vertex pancyclic

| volume = 20

| year = 1976| doi-access = free

}}.

• {{citation

| last1 = Hochbaum | first1 = Dorit S. | author1-link = Dorit S. Hochbaum

| last2 = Shmoys | first2 = David B. | author2-link = David Shmoys

| date = 1986

| doi = 10.1145/5925.5933

| issue = 3

| journal = Journal of the ACM

| location = New York, NY, USA

| pages = 533–550

| publisher = ACM

| title = A unified approach to approximation algorithms for bottleneck problems

| url = https://www.researchgate.net/publication/220430962

| volume = 33}}.

• {{citation

| last = Lau | first = H. T.

| location = Montreal

| publisher = McGill University

| series = Ph.D. thesis

| title = Finding a Hamiltonian cycle in the square of a block.

| year = 1980}}. As cited by {{harvtxt|Hochbaum|Shmoys|1986}}.

• {{citation

| last1 = Müttel | first1 = Janina

| last2 = Rautenbach | first2 = Dieter

| doi = 10.1016/j.disc.2012.07.032

| journal = Discrete Mathematics

| title = A short proof of the versatile version of Fleischner's theorem

| year = 2012| volume = 313

| issue = 19

| pages = 1929–1933

| doi-access = free

}}.

• {{citation

| last1 = Parker | first1 = R. Garey

| last2 = Rardin | first2 = Ronald L.

| doi = 10.1016/0167-6377(84)90077-4

| issue = 6

| journal = Operations Research Letters

| pages = 269–272

| title = Guaranteed performance heuristics for the bottleneck traveling salesman problem

| volume = 2

| year = 1984}}.

• {{citation

| last = Říha | first = Stanislav

| doi = 10.1016/0095-8956(91)90098-5

| issue = 1

| journal = Journal of Combinatorial Theory

| mr = 1109427

| pages = 117–123

| series = Series B

| title = A new proof of the theorem by Fleischner

| volume = 52

| year = 1991| doi-access = free

}}.

• {{citation

| last = Thomassen

| first = Carsten

| authorlink = Carsten Thomassen (mathematician)

| editor-first = B.

| editor-last = Bollobás

| editor-link = Béla Bollobás

| doi = 10.1016/S0167-5060(08)70512-0

| series = Annals of Discrete Mathematics

| mr = 499125

| pages = [https://archive.org/details/advancesingrapht0000camb/page/269 269–277]

| contribution = Hamiltonian paths in squares of infinite locally finite blocks

| publisher = Elsevier

| title = Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977)

| isbn = 978-0-7204-0843-0

| volume = 3

| year = 1978

| url = https://archive.org/details/advancesingrapht0000camb/page/269

}}.

• {{citation

| last = Underground | first = Polly | authorlink = Václav Chvátal

| doi = 10.1016/0012-365X(78)90164-4

| issue = 3

| journal = Discrete Mathematics

| mr = 522906

| page = 323

| title = On graphs with Hamiltonian squares

| volume = 21

| year = 1978| doi-access = free

}}.

• {{citation

| last = Bondy | first = J. A. | author-link = John Adrian Bondy

| contribution = Basic graph theory: paths and circuits

| location = Amsterdam

| mr = 1373656

| pages = 3–110

| publisher = Elsevier

| title = Handbook of combinatorics, Vol. 1, 2

| year = 1995}}.

• {{citation

| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand

| last2 = Lesniak | first2 = Linda

| last3 = Zhang | first3 = Ping | author3-link = Ping Zhang (graph theorist)

| edition = 5th

| isbn = 9781439826270

| page = 139

| publisher = CRC Press

| title = Graphs & Digraphs

| url = https://books.google.com/books?id=K6-FvXRlKsQC&pg=PA139

| year = 2010}}.

• {{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}}

Category:Theorems in graph theory