# Questions tagged [hamiltonian-graphs]

A Hamiltonian graph (directed or undirected) is a graph that contains a Hamiltonian cycle, that is, a cycle that visits every vertex exactly once.

94
questions

2
votes

1
answer

143
views

### Inspired by a card game: finding a path through $[\mathbb{N}]^n$

Motivation. Today my sons played a card game, in which a fixed number $n$ of cards was lying on the table. A move consists of adding an unused card to the cards on the table, and removing a card from ...

3
votes

1
answer

91
views

### Edge coloring of a graph on alternating groups

Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set $$S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\...

2
votes

2
answers

124
views

### Decompose complete directed graph with n vertices into n edge-disjoint cycles with length n−1

I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in Bermond and Faber - Decomposition of the ...

1
vote

1
answer

53
views

### Probability of randomly finding a loop in a (directed) Bernoulli random graph

This problem is inspired by an activity at work, where each person was tasked with introducing another person in the onboarding class, sequentially.
Problem Statement
Given $N$ people. For each pair ...

2
votes

1
answer

123
views

### Two ears polygon in a maximal planar hamiltonian graph

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...

1
vote

1
answer

84
views

### Is there a monograph or review of Hamiltonian cycles of graphs (or long cycles of graphs)？

In graph theory, a Hamiltonian cycle is a cycle that visits each vertex exactly once. Hamiltonian cycle has a long history, and I have followed some articles.
We can find plenty of examples of ...

3
votes

0
answers

56
views

### Hamilton cycles in Cayley graphs: between Rapaport-Strasser and Fleischner

A well-known question of Rapaport-Strasser asks whether every finite connected Cayley graph has a Hamilton cycle. Fleischner's Theorem implies that if $S$ is the generating set of such a Cayley graph $...

3
votes

0
answers

89
views

### Hamiltonian path in $\{0,1\}^n$ with rotations and bit-flip in position 0

We consider any non-negative integer as an ordinal, that is $0=\emptyset$ and $n=\{0,\ldots,n-1\}$ for every positive integer. Let $\{0,1\}^n$ denote the set of $\{0,1\}$-vectors of length $n$.
Define ...

9
votes

2
answers

1k
views

### Is this graph Hamiltonian?

Let $G$ be a simple $2$-connected graph with $m+n$ vertices ($n>m \geq 3$) with degree sequence $(m-1)^m$, $(n-1)^n$; that is, $G$ is degree-equivalent to two disjoint cliques $K_m$, $K_n$ of ...

6
votes

0
answers

99
views

### Hamilton cycles in random graphs with just enough connectivity

What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...

2
votes

1
answer

80
views

### Hamiltonian path in divisibility graph

Let $\mathbb{N}$ denote the set of positive integers, and consider the graph $(\mathbb{N}, E)$ where a set $\{a,b\}$ of two distinct positive integers belongs to $E$ if there is an integer $k>1$ ...

3
votes

0
answers

57
views

### Hamiltonian cycles in Cayley graph on alternating group

Let $G=\operatorname{Cay}(A_n,S)$ be the Cayley graph on the Alternating group $A_n\quad n\ge4$ with generating set $S=\{(1,2,3),(1,2,4),\ldots,(1,4,2),(1,3,2)\}$. One Hamiltonian cycle in $G$ for $n=...

6
votes

2
answers

285
views

### Hamiltonian path in bike-lock graph with $1$ known digit

Motivation. My youngest son has a bike lock with dials, and he forgot the unlocking combination completely, except that he remembered that digit $0$ appeared somewhere in the combination. So it was my ...

5
votes

0
answers

115
views

### How to construct 4-regular graphs with few Hamiltonian decompositions?

A Hamiltonian decomposition of a finite simple graph is a partition of its edge set so that each partition class forms a Hamiltonian cycle. This is only possible if the graph is $2k$-regular.
...

-1
votes

2
answers

120
views

### Path of length $n$ but no Hamilton cycle [closed]

What is an example of a simple graph $G = (\{1,\ldots,n\}, E)$, where $n\in\mathbb{N}$ is a positive integer, with the following properties?
There is a path in $G$ of length $n$,
every vertex has at ...

-1
votes

1
answer

87
views

### Hamiltonian $\mathbb{Z}$-paths in connected countably infinite vertex-transitive graphs [closed]

A simple, undirected graph $G=(V,E)$ is said to be vertex-transitive if for all $a,b\in V$ there is a graph isomorphism $\varphi:G\to G$ such that $\varphi(a) = b$.
If $G = (\omega, E)$ is vertex-...

13
votes

1
answer

619
views

### Generalisation of this circular arrangement of numbers from $1$ to $32$ with two adjacent numbers being perfect squares

I posted this question on MSE, and failed to get the type of answer I wanted. That's why I would like to post it here and wait for the experts to reply. Here's the link to the MSE post, which I ...

6
votes

0
answers

109
views

### Hamiltonicity for triangulations of the 3-sphere

A classical theorem of Whitney states that the 1-skeleton of every triangulation of the 2-sphere $\mathbb{S}^2$ has a Hamilton cycle as long as each of its 3-cycles bounds a triangle.
I'm wondering if ...

3
votes

1
answer

325
views

### The perfect matching problem of planar graph

We know that connectivity is closely related to the Hamiltonian of planar graphs.
The most famous result is the Tutte theorem.
Theorem (Tutte, 1956). A 4-connected planar graph has a Hamiltonian ...

1
vote

1
answer

100
views

### How to construct a hamilton-connected cubic graph? Is it possible?

If we are given a large integer $k$, can we construct a hamiltonian-connected $n$-vertex graph for every even $n\geq k$ such that all its vertices are of degree 3? Is there any reference concerning ...

1
vote

0
answers

77
views

### Number of pairs of edge-disjoint Hamilton cycles in complete graphs

Question:
how many pairs $\lbrace H_i, H_j\rbrace$ of edge-disjoint Hamilton cycles are in the complete graph $K_n$ with $n$ vertices?
while I could find information to the maximal number of edge-...

1
vote

0
answers

74
views

### Understanding the finale of the proof of Komlós' and Szemerédi's limit distribution of Hamiltonian random graphs

My question is about the end of the proof of Theorem 1 in [Komlós, Szemerédi (1983)], more precisely the arguments in Subsection 2.3. Let me state the beautiful theorem I am trying to understand in my ...

1
vote

1
answer

274
views

### Is every $k$-edge connected $k$-regular graph Hamiltonian?

A graph $G$ is Hamiltonian if there is a Hamiltonian cycle in $G$.
Suppose $G$ is a $k$-edge connected $k$-regular graph with $k>1$.
Does this ensure that $G$ is Hamiltonian?
If not, how about ...

1
vote

2
answers

145
views

### Hamiltonian cycle in $S_n$ with transpositions

For any set $X$, let $[X]^2=\{\{a,b\}:a\neq b \in X\}$. If $n\in\mathbb{N}$ is a positive integer, let $S_n$ denote the collection of bijections $\varphi:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$. Let $E_n\...

0
votes

0
answers

90
views

### Are there any necessary conditions of the existence of a Hamiltonian cycle on directed graphs

I'm trying to prove that one concrete directed graph has no Hamiltonian cycle, but didn't seem to find any relevant theorems

0
votes

0
answers

44
views

### Degree-constraints for the existence of vertex-disjoint directed cycle covers in digraphs

Given a digraph $G(E,V): (u,v)\in E\implies(v,u)\notin E$, what is known about lower bounds on the indegree and outdegree of the vertices that guarantee the existence of a vertex-disjoint directed ...

8
votes

2
answers

467
views

### Orthogonal Hamiltonian cycles in (n x n x n) grids

Let $C_n$ be a cubical $n \times n \times n$ subset of the integer lattice,
so consisting of $n^3$ vertices.
I am interested in special Hamiltonian cycles in $C_n$, special in the
sense that (a) each ...

2
votes

1
answer

259
views

### Opposite-nearest neighbor algorithm vs. nearest neighbor algorithm

Take the traveling salesman problem, but with three slight twists:
You can choose a different start vertex for each of the two algorithms.
Each path from one vertex to another is of unique, arbitrary ...

0
votes

1
answer

110
views

### Sources of information on algorithms for finding Hamiltonian cycles (Pósa)

I research various algorithms in complex networks and I am quite new in this field. I am currently focusing on random geometric graphs - Pósa's algorithm for finding a hamiltonian cycle. Can you ...

5
votes

1
answer

245
views

### Infinitely many counterexamples to Nash-Williams's conjecture about hamiltonicity?

Question from 2013
gives one counterexample to Nash-Williams's conjecture about hamiltonicity
of dense digraphs.
Later, we found tens of counterexamples on more than 30 vertices
and believe there are ...

2
votes

0
answers

107
views

### Two more counterexamples to a conjecture from 1975 about hamiltonicity of digraphs

Question from 2013
gives one counterexample to Nash-Williams's conjecture 1975 about hamiltonicity
of dense digraphs.
In the linked answer, @LouisD "reverse engineered" the counterexample
...

7
votes

3
answers

2k
views

### "Gray code" for building teams

Motivation. In a team of $n$ people, we had the task to build subteams of a fixed size $k<n$ such that every day, $1$ person of the subteam is replaced by another person in the team, but not in the ...

3
votes

0
answers

153
views

### Is this case of Barnette's Conjecture known?

Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my ...

1
vote

1
answer

158
views

### Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

Let $G$ be connected simple graph.
Clique cover of graph $G$ is partition of the vertices of $G$
into $k$ disjoint cliques $D'_i$.
Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle
in ...

4
votes

1
answer

99
views

### Does 2-connectivity imply Hamiltoniancy for subgraphs of the rook graph

We say the rook graph, $R_n$, is the cartesian product of $K_n \times K_n$. Let $S$ be the set of graphs that are an induced subgraph of $R_n$ for some $n$.
Does there exist some constant $c$ such ...

2
votes

1
answer

273
views

### Extending perfect matchings into Hamiltonian cycles

Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner ...

2
votes

1
answer

82
views

### The number of Hamiltonian circuits on a convex polytope embedded in $\mathbb{R}^N$

Recently I wondered whether there might be a natural topological complexity measure for convex polytopes embedded in $\mathbb{R}^N$. After some reflection it occurred to me that the number of distinct ...

6
votes

0
answers

68
views

### Normal colorings of bridgeless cubic graphs

Definition (informal) A normal edge-5-coloring of a bridgeless cubic graph $G$ is a proper 5 coloring of the edges of the graph, so that for each edge $e\in E(G)$, either $e$ and the four edges ...

8
votes

3
answers

527
views

### Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points

If $n>0$ is an integer, let $[n]=\{1,\ldots,n\}$. Let $S_n$ denote the set of all permutations (bijections) $\pi:[n]\to[n]$.
For which positive integers $n$ is there a bijection $\Phi:[n!]\to S_n$ ...

3
votes

1
answer

135
views

### Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)

Let $G$ be a simple cubic graph (that is, 3-regular). A dominating circuit of $G$ is a circuit $C$ such that each edge of $G$ has an endvertex in $C$. The circuit $C$ is chordless if no edge which is ...

1
vote

1
answer

5k
views

### Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

I am not expertise in graph theory. So have to ask this question here. The term "good" means that the algorithms should be efficient for general undirected simple connected graphs with a higher ...

14
votes

1
answer

896
views

### Are all cubic graphs almost Hamiltonian?

Call a graph $G$ $n$-almost-Hamiltonian if there is a closed walk in $G$ that visits every vertex of $G$ exactly $n$-times. So a Hamiltonian graph is $n$-almost-Hamiltonian for all $n$. Are all ...

4
votes

0
answers

156
views

### Is there a permutation $\pi\in S_n$ with $\sum\limits_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0$ for each $n>7$?

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each $n=8,9,\ldots$ we have
$$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{$*$}$$
for ...

12
votes

1
answer

381
views

### Quantitatively characterizing the failure of the converse of Dirac's theorem

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...

6
votes

1
answer

255
views

### What is the complexity of counting Hamiltonian cycles of a graph?

Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard.
Is it also $PP$-hard in the sense ...

7
votes

1
answer

184
views

### Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)

Many years ago, Grinberg found some uniquely-hamiltonian $3$-connected graphs, and published his results in a paper that has been cited several times as follows.
E. Grinberg, Three-connected graphs ...

4
votes

0
answers

138
views

### Halin Graphs with Highest Number of Hamilton Cycles

Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...

3
votes

0
answers

95
views

### Reference request: Bipartite symmetric graphs are hamiltonian

Does anyone know whether bipartite symmetric graphs are hamiltonian?
I'm not sure whether anyone have proved it before, but a nonhamiltonian symmetric bipartite graph would lead to a counterexample to ...

6
votes

1
answer

274
views

### Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...

9
votes

1
answer

389
views

### Are bipartite Moore graphs Hamiltonian?

This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first.
The cycles and complete bipartite graphs ...