# Tag Info

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 ...
• 11.2k
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,515
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 ...
• 34.2k
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 ...
• 14.8k

### 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 ...
• 53k
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. ...
• 28.8k
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$....
• 34.2k
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,691
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 ...
• 11.2k

### 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 ...
• 28.8k
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 ...
• 2,610

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

### "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,926
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 ...
• 34.2k

### 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,...
• 51.7k

• 34.2k
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.2k

### 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$ ...
• 13.1k
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 ...
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 ...
• 11.2k
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 ...
• 3,022
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 &...
• 413
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 ...
• 89.7k

### 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 ...
• 71

### 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,536

### 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 ...
• 145k
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 ...
• 7,292