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 ...
user avatar
  • 11.2k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 53k
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. ...
user avatar
  • 28.8k
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$....
user avatar
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 ...
user avatar
  • 2,691
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 ...
user avatar
  • 11.2k
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 ...
user avatar
  • 28.8k
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 ...
user avatar
  • 2,610
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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,...
user avatar
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\...
user avatar
  • 8,761
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 $...
user avatar
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$, ...
user avatar
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$ ...
user avatar
  • 13.1k
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 ...
user avatar
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 ...
user avatar
  • 11.2k
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 ...
user avatar
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 &...
user avatar
  • 413
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 ...
user avatar
  • 89.7k
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 ...
user avatar
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, ...
user avatar
  • 1,536
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 62.1k

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