20
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 ...

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 ...

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 ...

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 ...

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 ...

10
votes

Accepted

### How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?

I will rephrase your question slightly. Let $K_{n}^{*}$ be the directed graph with $n$ vertices and two oppositely directed edges for each pair of vertices. Your question is then the following.
...

10
votes

Accepted

### How many edges can be added to two circles before the graph becomes Hamiltonian?

If a full set of $n$ edges is inserted between the cycles, what you have is a "cycle permutation graph". According to this paper, there are nonhamiltonian cycle permutation graphs for all odd $n\ge 9$....

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 ...

9
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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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,...

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\...

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 $...

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$, ...

5
votes

### Can we find 3 disjoint directed Hamiltonian cycles in the cube?

This is what I managed to figure out via google. In "Decompositions into cycles I, Hamilton Decompositions" by Alspach, Bermond and Sotteau (google books link) of 1990, a regular graph $G$ ...

5
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 ...

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 ...

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 ...

5
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
&...

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 ...

4
votes

### Efficient Hamiltonian cycle algorithms for graph classes

In fact, it can be proved that Hamiltonian Cycle remains $\mathsf{NP}$-hard even for a very restricted subclass of line graphs: line graphs of $1$-subdivisions of planar cubic bipartite graphs. These ...

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, ...

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 ...

4
votes

Accepted

### What is the densest bipartite graph with unique Hamiltonian cycle?

The OP asks for the densest bipartite graph having a exactly one Hamiltonian cycle. We remark that in Graphs with exactly one Hamiltonian cycle, John Sheehan shows that a graph on $n$ vertices with ...

4
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 ...

4
votes

Accepted

### Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?

If one takes a planar cubic non-Hamiltonian graph, and takes the vertex connect sum of 3 copies, then it cannot have such a 2-factor. It's not hard to check that a vertex connect sum of such graphs is ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

hamiltonian-graphs × 86graph-theory × 77

co.combinatorics × 32

hamiltonian-paths × 14

reference-request × 8

computational-complexity × 6

random-graphs × 4

bipartite-graphs × 4

nt.number-theory × 3

algorithms × 3

discrete-geometry × 3

recreational-mathematics × 3

counterexamples × 3

extremal-graph-theory × 3

perfect-matchings × 3

directed-graphs × 3

hypercube × 3

pr.probability × 2

convex-polytopes × 2

graph-colorings × 2

permutations × 2

infinite-combinatorics × 2

combinatorial-optimization × 2

spectral-graph-theory × 2

sparse-matrices × 2