All Questions
Tagged with hamiltonian-graphs graph-theory
102 questions
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
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
14
votes
1
answer
1k
views
Are all cubic graphs almost Hamiltonian?
Call a graph $G$ $n$-almost-Hamiltonian if there is a closed walk in $G$ that visits every vertex of $G$ exactly $n$-times. So a Hamiltonian graph is $n$-almost-Hamiltonian for all $n$. Are all ...
- 5,349
14
votes
1
answer
783
views
What was Smith's proof of Smith's theorem on Hamilton cycles in cubic graphs?
In a short 1946 paper "On Hamiltonian Circuits", Tutte proved the famous result that an edge in a cubic graph lies in an even number of Hamilton circuits.
He attributed the result to his friend CAB ...
- 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
12
votes
1
answer
424
views
Quantitatively characterizing the failure of the converse of Dirac's theorem
First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...
- 221
12
votes
1
answer
2k
views
Hobbled rook tour – Hamiltonian cycle on square grid
Consider a square grid of even side length ($2n \times 2n$). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...
- 121
11
votes
1
answer
328
views
How many edges can be added to two circles before the graph becomes Hamiltonian?
Start with two $n$-circles $(v_1\cdots v_n)$ and $(w_1\cdots w_n)$ of vertice sets $V$ and $W$, where $n\ge 5$. Add a number of vertex-disjoint edges between $V$ and $W$ (thus no chords) in a way ...
- 13.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
10
votes
1
answer
513
views
What is the complexity of finding a third Hamilton Cycle in cubic graph?
According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known ...
user39815
9
votes
2
answers
2k
views
Is this graph Hamiltonian?
Let $G$ be a simple $2$-connected graph with $m+n$ vertices ($n>m \geq 3$) with degree sequence $(m-1)^m$, $(n-1)^n$; that is, $G$ is degree-equivalent to two disjoint cliques $K_m$, $K_n$ of ...
- 105
9
votes
2
answers
2k
views
"Gray code" of all permutations
Informally asking, can we step through all permutations of the set $\{1,\ldots,n\}$ by just using transpositions?
More formally: For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be ...
- 48.9k
9
votes
1
answer
399
views
Are bipartite Moore graphs Hamiltonian?
This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first.
The cycles and complete bipartite graphs ...
- 9,501
9
votes
0
answers
245
views
Heuristic arguments regarding Sheehan's conjecture?
Sheehan conjectured that there are no 4-regular graphs that are uniquely hamiltonian (i.e. have exactly one hamilton cycle).
Evidence that might be loosely seen to be in favour of this conjecture is: ...
- 12.7k
8
votes
2
answers
598
views
Orthogonal Hamiltonian cycles in (n x n x n) grids
Let $C_n$ be a cubical $n \times n \times n$ subset of the integer lattice,
so consisting of $n^3$ vertices.
I am interested in special Hamiltonian cycles in $C_n$, special in the
sense that (a) each ...
- 151k
8
votes
2
answers
2k
views
How to efficiently find a Hamiltonian cycle in a graph whose closure is complete?
A graph whose closure is the complete graph is Hamiltonian by the Bondy-Chvátal theorem, but I haven't found a polynomial algorithm for finding a Hamiltonian cycle in such a graph. Is there one that ...
8
votes
0
answers
123
views
Is there a non-bipartite hamiltonian cubic graph on $n$ vertices with no $(n-1)$-cycle?
Is there a cubic (3-regular) graph $G$ on $n$ vertices such that:
$G$ is hamiltonian
$G$ has no $(n-1)$-cycles
$G$ is not bipartite
My computer tells me that there are none on up to $24$ vertices.
- 12.7k
7
votes
3
answers
2k
views
"Gray code" for building teams
Motivation. In a team of $n$ people, we had the task to build subteams of a fixed size $k<n$ such that every day, $1$ person of the subteam is replaced by another person in the team, but not in the ...
- 48.9k
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
7
votes
1
answer
210
views
Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)
Many years ago, Grinberg found some uniquely-hamiltonian $3$-connected graphs, and published his results in a paper that has been cited several times as follows.
E. Grinberg, Three-connected graphs ...
- 12.7k
7
votes
1
answer
736
views
Refinement of Dirac's theorem on Hamiltonian graphs
Dirac's theorem states that if degree of each vertex of a graph $G=(V,E)$ is not less than $|V|/2$, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I ...
- 109k
6
votes
1
answer
299
views
Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?
In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
- 155
6
votes
2
answers
304
views
Hamiltonian path in bike-lock graph with $1$ known digit
Motivation. My youngest son has a bike lock with dials, and he forgot the unlocking combination completely, except that he remembered that digit $0$ appeared somewhere in the combination. So it was my ...
- 48.9k
6
votes
1
answer
243
views
Hamiltonicity criteria for sparse graphs
Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).
There are three main classes of criteria for Hamiltonicity that I am aware of:
Dirac-...
- 6,962
6
votes
1
answer
335
views
What is the complexity of counting Hamiltonian cycles of a graph?
Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard.
Is it also $PP$-hard in the sense ...
- 121
6
votes
1
answer
344
views
Hamiltonian cycles in power-graphs
I've stumbled across a short note from 1993 where a nice question was asked: Suppose you take a graph with vertices $\{1,2,\ldots,n\}$ and connect $i,j$ by an edge if and only if $i+j$ is a $k$th ...
- 6,962
6
votes
0
answers
164
views
Hamilton cycles in random graphs with just enough connectivity
What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
- 7,545
6
votes
0
answers
73
views
Normal colorings of bridgeless cubic graphs
Definition (informal) A normal edge-5-coloring of a bridgeless cubic graph $G$ is a proper 5 coloring of the edges of the graph, so that for each edge $e\in E(G)$, either $e$ and the four edges ...
- 1,018
6
votes
0
answers
129
views
Minimum number of hamilton cycles in a 4-connected planar triangulation?
I am currently interested in hamilton cycles (i.e. a cycle through every vertex) in planar triangulations (i.e. planar graphs with every face a triangle).
There are non-hamiltonian planar ...
- 12.7k
6
votes
0
answers
76
views
Cage graphs and even cycles
Let $G$ be a $(\nu,g)$-cage graph of degree $\nu$ with girth $g$ and $n=n(\nu,g)$ vertices.
Based on the known examples, I am wondering if the following can be proved/disproved:
Is it true that ...
- 13.4k
6
votes
0
answers
108
views
Localizing Bondy's metaconjecture on hamiltonicity
Definitions:
Let $G$ be a graph on $n$ vertices. $G$ is Hamiltonian provided $G$ has a cycle of length $n$. $G$ is pancyclic provided $G$ has a cycle of length $\ell$ for every $3 \leq \ell \leq n$.
...
- 399
5
votes
2
answers
191
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
5
votes
1
answer
1k
views
How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?
The question started from a problem brought home by a friend's 5th grader: "How many ways can you seat 5 people around a round table so that the people sitting to the left of any person is different ...
- 2,205
5
votes
1
answer
224
views
Reconstructing the number of Hamiltonian cycles
As is common terminology in graph reconstruction, given a graph $G$, we call a vertex deleted subgraph of $G$, a card, and call the multiset of all cards, the deck of $G$. The graph reconstruction ...
- 85.6k
5
votes
1
answer
271
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
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
1
answer
119
views
Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every triangle in $G$ has an edge in $C$
Let $G$ be a $k$-connected planar triangulation ($k\geq 4$) and let $C$ be a Hamilton cycle of $G$. Then:
Which conditions would be sufficient to assure that every triangle of $G$ has at least one ...
5
votes
0
answers
127
views
Do uniquely Hamiltonian graphs have cycles of a sufficiently long length?
Let $C$ be a Hamiltonian cycle of a graph $G$.
Call an edge $e$ of $G$ a chord if $e\not\in C$.
Let each edge of $C$ be weighted $1$ and each chord be weighted $2$.
The weight of a path or cycle of ...
- 673
5
votes
0
answers
154
views
How to construct 4-regular graphs with few Hamiltonian decompositions?
A Hamiltonian decomposition of a finite simple graph is a partition of its edge set so that each partition class forms a Hamiltonian cycle. This is only possible if the graph is $2k$-regular.
...
- 13.6k
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
5
votes
0
answers
295
views
A digraph related to permutations
A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence.
Consider the following ...
- 17.6k
4
votes
2
answers
349
views
Can we find 3 disjoint directed Hamiltonian cycles in the cube?
Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.
Can we partition the edges of $D$ into $d$ ...
- 19.1k
4
votes
3
answers
506
views
Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?
Consider simple bridgeless cubic planar graphs.
Does each such graph admit a 2-factorization with $\leq 2$ components each of which has even order?
If not, does anyone know of an counterexample?
...
- 443
4
votes
1
answer
109
views
Does 2-connectivity imply Hamiltoniancy for subgraphs of the rook graph
We say the rook graph, $R_n$, is the cartesian product of $K_n \times K_n$. Let $S$ be the set of graphs that are an induced subgraph of $R_n$ for some $n$.
Does there exist some constant $c$ such ...
- 3,499
4
votes
1
answer
724
views
Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph
It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard.
By Smith's theorem, ...
- 2,993
4
votes
1
answer
228
views
Probability problem in Sheehan's conjecture
As my first math project, I have been working on Sheehan's Conjecture
and am stuck for weeks. I wonder if I am at a dead end.
Sheehan's Conjecture states that every Hamiltonian 4-regular simple
graph ...
- 43
4
votes
0
answers
69
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 ...
- 1,851
4
votes
0
answers
234
views
How many 20-vertex 2-connected 5-regular non-Hamiltonian graphs are there?
As for the question in title, I attempted to use nauty to obtain them, but it has been running on my computer for nearly three days without producing any results.
<...
- 1,851
4
votes
0
answers
230
views
Is this case of Barnette's Conjecture known?
Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my ...
- 3,499
4
votes
0
answers
143
views
Halin Graphs with Highest Number of Hamilton Cycles
Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...
- 13.2k