21
votes
Accepted
Is this graph Hamiltonian?
Here is a 9-vertex graph with degree sequence 4 4 4 4 4 3 3 3 3 that does not have a Hamilton cycle (because it is bipartite on an odd number of vertices).
Edit: Here is one line of SageMath showing ...
- 12.7k
19
votes
Accepted
Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points
We are basically looking at the Cayley graph of $S_n$ where the generating set is the set of all derangements. The question is whether this graph is Hamiltonian.
I will quote here a paper by ...
- 4,713
15
votes
Accepted
Are all cubic graphs almost Hamiltonian?
Yes, every connected cubic graph is 3-almost-Hamiltonian.
Replace each edge by two parallel edges then follow an Eulerian circuit.
In the case of a bridgeless cubic graph, you can add a perfect ...
- 37.7k
12
votes
Accepted
"Gray code" of all permutations
From V. L. Kompel'makher and V. A. Liskovets, "Sequential generation of arrangements by means of a basis of transpositions", Kibernetika 3, 17, May-June, 1975:
It is well known ([1], p. 28) that ...
- 15.4k
11
votes
Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points
it is still of interest to me, I would be glad to hear about it!
OK, sorry for the delay. This elementary argument is, probably, well-known but I was too lazy to make a thorough search, so if ...
- 61.9k
10
votes
Accepted
What is the smallest uniquely hamiltonian graph with minimum degree at least 3?
The system encouraged me to answer my own question, although it feels a bit strange to do so.
Anyway, after a bit of thinking and a (more substantial) bit of computing, I can now safely conclude that ...
- 12.7k
10
votes
Accepted
"Gray code" for building teams
This seems to be possible for all choices of $k$ and $n$. I found a page here by Dr. Ronald D. BAKER describing a more than sixty year old 'revolving door algorithm'.
When enumerating the k-element ...
- 2,821
9
votes
Accepted
Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?
The $n$-dimensional analogue of the octahedron is the complement of a perfect matching of its vertex set. (Every vertex is joined to every other vertex except its antipode.) If you take a Hamilton ...
- 3,451
9
votes
What is the smallest uniquely hamiltonian graph with minimum degree at least 3?
I am not sure what the smallest such graph is, but since you also asked for more information on uniquely hamiltonian graphs with minimum degree $3$, Entringer and Swart proved the following nice ...
- 32.1k
8
votes
Orthogonal Hamiltonian cycles in (n x n x n) grids
In the recent book "Bicycle or Unicycle?" by Velleman and Wagon, this is problem #16 "Wiggle Room." (Actually, there it's generalized to computing the maximum length path, with a ...
- 133
7
votes
"Gray code" for building teams
The following recursive description of a revolving door sequence is taken from here, where it is also proved that it generates a Hamilton cycle. The $k$-subsets of $\{1,\dots,n\}$ are identified with ...
- 2,966
7
votes
Accepted
Inspired by a card game: finding a path through $[\mathbb{N}]^n$
$[\mathbb{N}]^n$, with edges between $a,b\in[\mathbb{N}]^n$ if $\#(a\cap b)=n-1$, is an infinite graph in which all vertices have infinite degree. Moreover, for any two vertices $a,b$ in $[\mathbb{N}]^...
- 10.6k
7
votes
Accepted
Properties of Hamilton cycles in hypercubes
If there is a set of $2^{n-1}$ mutually parallel edges, then it is unique by the pigeonhole principle: a Hamilton cycle has $2^n$ edges, and contains at least one edge in each "direction".
...
- 2,671
6
votes
Accepted
What is the complexity of finding a third Hamilton Cycle in cubic graph?
Thomason's algorithm surely is superpolynomial, and shows that the problem is in PPA. In [3] I described another algorithm, also exponential and shows PPA, which is just as simple and has the added ...
- 234
6
votes
Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points
For $n=4$ it is doable. A Hamiltonian cycle is
$$[[1, 2, 3, 4], [2, 1, 4, 3], [1, 3, 2, 4], [2, 4, 1, 3], [1, 3, 4, 2], [2, 1, 3, 4], [1, 2, 4, 3], [2, 3, 1, 4], [1, 4, 2, 3], [2, 3, 4, 1], [1, 4, 3,...
- 54.2k
6
votes
Accepted
Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)
This is a NEW EDITION using the condition that two edges incident with a vertex not in the dominating circuit cannot be attached to consecutive vertices in the dominating circuit.
I tried 200 million ...
- 37.7k
6
votes
"Gray code" for building teams
Theorem. The graph $G(n,k)$ is Hamiltonian if $n\ge3$ and $0\lt k\lt n$.
Proof. If $k=1$ or $k=n-1$ it's obvious, because $G(n,k)\cong K_n$ in those cases. Now consider the graph $G=G(n,k)$ where $2\...
- 13.4k
6
votes
Accepted
Hamiltonian path in bike-lock graph with $1$ known digit
If $k=2$, then a Hamiltonian path is constructed easily.
In the case $k=3$ and $n\equiv1\pmod2$ a Hamiltonian path is constructed as follows:
\begin{align*}\label{cycle}
%%%%%%%%%%%%%%% x=0
&...
- 673
5
votes
Accepted
Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)
I have now resolved most of the mysteries, and as MO prompts me to answer my own question, I am now doing so even though it feels a bit odd.
After some false starts with expired email addresses, I ...
- 12.7k
5
votes
"Gray code" of all permutations
In Knuth's second fascicle of volume 4 of The Art of Computer Programming, he gives "algorithm P" (or more colloquially, the method of plain changes) for generating the permutations of a sequence with ...
5
votes
Hamiltonicity and minimal degree in bipartite graphs
Take any $k\ge 1$ and four disjoint sets of vertices $A,B,C,D$ with $|A|=|D|=k+2$, $|B|=|C|=k$. Completely join $A$ to $B$, $B$ to $C$ and $C$ to $D$. This gives a bipartite graph of minimum degree $...
- 37.7k
5
votes
Accepted
Number Associated with Straight-line Drawings of Hamiltonian Graphs
It is known that the number of non-crossing spanning cycles (called "simple polygonalizations") of $n$ points in the plane can be as low as $1$ (for points in convex position) and as high as $4.64^n$, ...
- 18.6k
5
votes
Accepted
Orthogonal Hamiltonian cycles in (n x n x n) grids
Partial answer: It is possible for $C_n$ if $n$ is a power of two.
$C_2$ and $C_4$ are shown in the question. For larger $n$ the idea is to take a three-dimensional Moore curve (a recursive ...
- 4,219
5
votes
Accepted
Is every $k$-edge connected $k$-regular graph Hamiltonian?
Assume $k \geq 4$, since, for $k=2$, the answer for both questions is yes, and for $k=3$, no, as there's the Petersen graph.
The answer to the first question is no. To see this, we only need to prove ...
- 9,501
5
votes
Accepted
Hamiltonian path in divisibility graph
Yes, as for every countable graph on which any two vertices have infinitely many common neighbours. If you constructed a path $v_1\ldots v_m$, and $u$ is the first (with respect to a numeration chosen ...
- 109k
5
votes
Accepted
Number of Hamiltonian cycles on 24-cell graph
The Held-Karp algorithm for TSP can be modified to count Hamiltonian cycles. The idea is to fix a starting vertex $v \in V$ and inductively count, for every vertex $w \neq v$ and subset $S \subseteq V$...
- 12.4k
5
votes
Number of Hamiltonian cycles on 24-cell graph
We can run the code from github due to Jorik Jooken. The folder contains an algorithm ("countHamiltonianCyclesHeldKarp") for counting the number of Hamiltonian cycles (based on the Held-...
- 1,851
5
votes
Accepted
Approximation of Hamiltonian cycles
Claim. For every $\rho \geq 1$, there is no polynomial $\rho$-approximation algorithm for $\texttt{MinHalfSimpCycle}$, unless P=NP.
Proof. Let $G$ be an instance of the Travelling Salesman Problem (...
- 32.1k
4
votes
Number Associated with Straight-line Drawings of Hamiltonian Graphs
Slightly later, and less formally published reference, than David E.'s citation:
Sharir, Micha, Adam Sheffer, and Emo Welzl. "Counting plane graphs: Perfect matchings, spanning cycles, and ...
- 151k
4
votes
A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?
I realize this question was asked seven years ago and hasn't had a comment in four years, but I just came across it and thought it might be worth sharing what I've learned.
As @HughThomas mentions, ...
- 1,701
Only top scored, non community-wiki answers of a minimum length are eligible