Questions tagged [hamiltonian-graphs]
A Hamiltonian graph (directed or undirected) is a graph that contains a Hamiltonian cycle, that is, a cycle that visits every vertex exactly once.
118 questions
17
votes
5
answers
1k
views
Joshua Lederberg's influence on graph theory
Joshua Lederberg received a the Nobel prize in medicine in 1958 and he was a major contributor to the Stanford DENDRAL software expert system that
Given a mass spectrum of an organic molecular sample ...
- 14.3k
2
votes
0
answers
110
views
Is there a chordal graph whose toughness is exactly $\frac{3}{2}$ and which is non-Hamiltonian?
Kratsch once asked whether every $\frac{3}{2}$-tough chordal graph is Hamiltonian. This question was answered in the negative by Bauer et al., [1] who constructed a family of non-Hamiltonian chordal ...
- 2,131
0
votes
0
answers
167
views
Can one construct a 5-connected, 5-regular, bipartite, 1-planar graph that is non-Hamiltonian?
A 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point.
Barnette's conjecture states that every 3-connected cubic bipartite ...
- 2,131
1
vote
0
answers
85
views
Does a cycle plus triangles graph have a compatible cycle decomposition?
Let $G$ be a 4-regular graph that can be decomposed as a Hamiltonian cycle and triangles. Does it always have a cycle decomposition that is compatible with the cycle plus triangles decomposition? Two ...
- 61
2
votes
0
answers
170
views
First occurrence of unique Hamiltonian cycles/graphs
It is very well known that finding a hamiltonian cycle has its origins in the Icosian game due to Sir William Rowan Hamilton.
I have been wanting to know when was the first instance when a unique ...
4
votes
1
answer
144
views
Variant of Hamiltonian Cycle where vertices (but not edges) may appear more than once
I am interested in the following problem:
Given any finite connected graph we want to know if there exists a closed walk such that each vertex of the graph appears AT LEAST once and no edge is ...
-1
votes
1
answer
174
views
How to prove Ore's condition stronger than Posa's condition?
in sufficient conditions of Hamiltonian graphs,it is well known that Ore's condition is stronger than Posa's condition. how to prove it?
5
votes
1
answer
180
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 2,131
5
votes
1
answer
464
views
Approximation of Hamiltonian cycles
Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
- 53
0
votes
0
answers
134
views
Uniqueness of compatible cycle decomposition for Eulerian trail
Fleischner mentions in his article Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs about the uniqueness of compatible cycle decomposition that ...
3
votes
1
answer
212
views
Has there been progress on Hamiltonicity in 4-connected claw-free graphs with a constant maximum degree?
In 1984, Matthews and Sumner [1] conjectured that every 4-connected claw-free graph is Hamiltonian, and this conjecture is still wide open.
I would like to know if there has been any progress on this ...
- 2,131
3
votes
1
answer
406
views
Properties of Hamilton cycles in hypercubes
Questions:
is the following true?
for $n\in\mathbb{N}$ every Hamilton cycle in an $n$-dimensional hypercube $Q_n$ there exist $2^{n-1}$ edges that are mutually parallel
$Q_2$ is the only case in ...
- 14.3k
2
votes
0
answers
144
views
15-game graph contains a Hamiltonian path ? Lovász conjecture for groupoids, loops, quasigroups , etc?
Typically Cayley graphs are defined for groups and generators sets S. But basically one only needs some set S and another set V and partially defined operation SxV->V, then one defines graph with ...
- 26.6k
5
votes
2
answers
388
views
Number of Hamiltonian cycles on 24-cell graph
I asked Wolfram Alpha for the number of Hamiltonian cycles on the 24-cell graph.
https://www.wolframalpha.com/input?i=number+of+hamiltonian+cycles+on+24-cell+graph
It answers 114.9 billion but doesn't ...
- 53
0
votes
0
answers
83
views
Are there 4-connected planar non-hamilton multi-graphs?
Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
- 2,131