Skip to main content
added 284 characters in body
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Here is the abstract of a talk that Herbert Fleischner gave at CombinaTexas: Combinatorics in the South-Central U.S., available at this link, in 2003. The title of his talk was, "Uniquely Hamiltonian Graphs":

Abstract: In the 1970s, J.Sheehan asked whether there are 4-regular simple graphs having precisely one Hamiltonian cycle (= uniquely Hamiltonian graphs). In the early 1990s, 4-regular loopless uniquely Hamiltonian multigraphs were constructed whose underlying uniquely Hamiltonian (simple) graphs have 3- and 4-valent vertices only. C.Thomassen showed that regular graphs of sufficiently high degree cannot be uniquely Hamiltonian; and J.A.Bondy, in his article for the Handbook of Combinatorics, asked whether uniquely Hamiltonian graphs must have a vertex of degree 2 or 3. Starting from the examples quoted above, one can construct Eulerian uniquely Hamiltonian graphs of minimum degree 4.

See also The Open Problems Garden, "Uniquely Hamiltonian graphs," which highlights the conjecture:

If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely Hamiltonian.

Here is the abstract of a talk that Herbert Fleischner gave at CombinaTexas: Combinatorics in the South-Central U.S., available at this link, in 2003. The title of his talk was, "Uniquely Hamiltonian Graphs":

Abstract: In the 1970s, J.Sheehan asked whether there are 4-regular simple graphs having precisely one Hamiltonian cycle (= uniquely Hamiltonian graphs). In the early 1990s, 4-regular loopless uniquely Hamiltonian multigraphs were constructed whose underlying uniquely Hamiltonian (simple) graphs have 3- and 4-valent vertices only. C.Thomassen showed that regular graphs of sufficiently high degree cannot be uniquely Hamiltonian; and J.A.Bondy, in his article for the Handbook of Combinatorics, asked whether uniquely Hamiltonian graphs must have a vertex of degree 2 or 3. Starting from the examples quoted above, one can construct Eulerian uniquely Hamiltonian graphs of minimum degree 4.

Here is the abstract of a talk that Herbert Fleischner gave at CombinaTexas: Combinatorics in the South-Central U.S., available at this link, in 2003. The title of his talk was, "Uniquely Hamiltonian Graphs":

Abstract: In the 1970s, J.Sheehan asked whether there are 4-regular simple graphs having precisely one Hamiltonian cycle (= uniquely Hamiltonian graphs). In the early 1990s, 4-regular loopless uniquely Hamiltonian multigraphs were constructed whose underlying uniquely Hamiltonian (simple) graphs have 3- and 4-valent vertices only. C.Thomassen showed that regular graphs of sufficiently high degree cannot be uniquely Hamiltonian; and J.A.Bondy, in his article for the Handbook of Combinatorics, asked whether uniquely Hamiltonian graphs must have a vertex of degree 2 or 3. Starting from the examples quoted above, one can construct Eulerian uniquely Hamiltonian graphs of minimum degree 4.

See also The Open Problems Garden, "Uniquely Hamiltonian graphs," which highlights the conjecture:

If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely Hamiltonian.

Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Here is the abstract of a talk that Herbert Fleischner gave at CombinaTexas: Combinatorics in the South-Central U.S., available at this link, in 2003. The title of his talk was, "Uniquely Hamiltonian Graphs":

Abstract: In the 1970s, J.Sheehan asked whether there are 4-regular simple graphs having precisely one Hamiltonian cycle (= uniquely Hamiltonian graphs). In the early 1990s, 4-regular loopless uniquely Hamiltonian multigraphs were constructed whose underlying uniquely Hamiltonian (simple) graphs have 3- and 4-valent vertices only. C.Thomassen showed that regular graphs of sufficiently high degree cannot be uniquely Hamiltonian; and J.A.Bondy, in his article for the Handbook of Combinatorics, asked whether uniquely Hamiltonian graphs must have a vertex of degree 2 or 3. Starting from the examples quoted above, one can construct Eulerian uniquely Hamiltonian graphs of minimum degree 4.