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.3k
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,618
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.2k
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.3k
11
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$....
- 37.2k
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 ...
- 59.8k
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.3k
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,743
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,421
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 ...
- 31.5k
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,946
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}]^...
- 8,076
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
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.2k
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,...
- 53.6k
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\...
- 11.9k
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.3k
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.2k
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
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.5k
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 ...
- 3,964
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,421
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 ...
- 103k
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 ...
- 66.8k
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 ...
- 149k
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 ...
- 71
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,666
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 ...
- 7,775
Only top scored, non community-wiki answers of a minimum length are eligible