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.
10 questions
0
votes
1
answer
1k
views
Does this graph contain at least two Hamiltonian cycles?
Let $G$ be a simple graph which is a $2n$-cycle together with $n$ chords such that $G$ is $3$-regular. In other words, the set of $n$ chords is a perfect matching of $G$.
I conjecture that for every ...
- 421
16
votes
1
answer
696
views
A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?
Maybe I am missing something, but found potential counterexample to a conjecture
of Nash-Williams.
According to HAMILTONIAN DEGREE SEQUENCES IN DIGRAPHS
The outdegree and indegree sequences of ...
- 25.4k
10
votes
2
answers
782
views
Graphs with many edges avoided by Hamiltonian cycles
Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...
- 13.4k
15
votes
2
answers
2k
views
What is the smallest uniquely hamiltonian graph with minimum degree at least 3?
I would like to know more about uniquely hamiltonian graphs with minimum vertex degree at least 3, and in particular what is the smallest one.
(Recall that a graph is hamiltonian if it has a cycle ...
- 12.7k
13
votes
1
answer
1k
views
Generalisation of this circular arrangement of numbers from $1$ to $32$ with two adjacent numbers being perfect squares
I posted this question on MSE, and failed to get the type of answer I wanted. That's why I would like to post it here and wait for the experts to reply. Here's the link to the MSE post, which I ...
- 791
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an ...
- 6,962
5
votes
1
answer
279
views
Infinitely many counterexamples to Nash-Williams's conjecture about hamiltonicity?
Question from 2013
gives one counterexample to Nash-Williams's conjecture about hamiltonicity
of dense digraphs.
Later, we found tens of counterexamples on more than 30 vertices
and believe there are ...
- 25.4k
5
votes
0
answers
99
views
Graph gadget related to uniquely hamiltionian regular graphs
A graph is uniquely hamiltonian if it has exactly one hamiltonian cycle.
According to a conjecture there are no $r$-regular uniquely hamiltonian
graphs for $r > 2$ and of special interest is the ...
- 25.4k
3
votes
1
answer
239
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 ...
- 13.2k
2
votes
0
answers
116
views
Two more counterexamples to a conjecture from 1975 about hamiltonicity of digraphs
Question from 2013
gives one counterexample to Nash-Williams's conjecture 1975 about hamiltonicity
of dense digraphs.
In the linked answer, @LouisD "reverse engineered" the counterexample
...
- 25.4k