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

107
questions

0
votes

0
answers

26
views

### A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial

We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle.
Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...

0
votes

0
answers

36
views

### Are there 4-connected planar non-hamilton multi-graphs?

Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...

1
vote

0
answers

52
views

### A generalized/set hamiltonian cycle problem on directed graphs

So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...

4
votes

1
answer

167
views

### Probability problem in Sheehan's conjecture

As my first math project, I have been working on Sheehan's Conjecture
and am stuck for weeks. I wonder if I am at a dead end.
Sheehan's Conjecture states that every Hamiltonian 4-regular simple
graph ...

0
votes

0
answers

48
views

### Clique sizes of generalized Kneser graphs

Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common ...

0
votes

0
answers

55
views

### Cycles in Kneser graphs with three vertices forming triangles

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...

5
votes

0
answers

113
views

### Do uniquely Hamiltonian graphs have cycles of a sufficiently long length?

Let $C$ be a Hamiltonian cycle of a graph $G$.
Call an edge $e$ of $G$ a chord if $e\not\in C$.
Let each edge of $C$ be weighted $1$ and each chord be weighted $2$.
The weight of a path or cycle of ...

1
vote

1
answer

85
views

### Existence of a strongly regular vertex ordering on cubic graphs

Definition: Let $G=(V,E)$ be a cubic (i.e. $3$-regular) graph, and $<$ a total order on $V$. For $v\in V$ let $v^\downarrow$ denote the set of nodes $w\in V$ such that $w<v$, and let $\alpha(v) =...

2
votes

0
answers

87
views

### Constructing Hamiltonian circuits in acyclic digraphs

Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges.
Q. Is there a method to minimize the addition of edges to achieve a ...

0
votes

0
answers

57
views

### Non-planar non-Hamiltonian chordal graphs with toughness greater than 1

The following article tells us that every planar chordal graph with toughness greater than 1 is Hamiltonian.
Böhme T, Harant J, Tkáč M. More than one tough chordal planar graphs are Hamiltonian[J]. ...

2
votes

2
answers

61
views

### Does $(\omega, E)$ with the cycle condition have an $\omega$-path?

Let $G = (V,E)$ be a simple, undirected graph. We say that $v\neq w\in V$ lie on a common cycle if there is an integer $n\geq 3$ and an injective graph homomorphism $f: C_n\to V$ such that $v,w\in \...

5
votes

1
answer

106
views

### Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every triangle in $G$ has an edge in $C$

Let $G$ be a $k$-connected planar triangulation ($k\geq 4$) and let $C$ be a Hamilton cycle of $G$. Then:
Which conditions would be sufficient to assure that every triangle of $G$ has at least one ...

4
votes

0
answers

204
views

### How many 20-vertex 2-connected 5-regular non-Hamiltonian graphs are there?

As for the question in title, I attempted to use nauty to obtain them, but it has been running on my computer for nearly three days without producing any results.
<...

2
votes

1
answer

164
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

100
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

197
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

63
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

128
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

93
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

65
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

101
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

2k
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

136
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

98
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

67
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

295
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

143
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

170
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

94
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

903
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

121
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

498
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

114
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

157
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

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

2
votes

1
answer

388
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

169
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

115
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

55
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

556
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

280
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

111
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

269
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

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

4
votes

0
answers

207
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

172
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

104
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

310
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

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