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.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12 votes
1 answer
2k views

Hobbled rook tour – Hamiltonian cycle on square grid

Consider a square grid of even side length ($2n \times 2n$). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...
John's user avatar
  • 121
9 votes
0 answers
224 views

Heuristic arguments regarding Sheehan's conjecture?

Sheehan conjectured that there are no 4-regular graphs that are uniquely hamiltonian (i.e. have exactly one hamilton cycle). Evidence that might be loosely seen to be in favour of this conjecture is: ...
Gordon Royle's user avatar
  • 12.3k
8 votes
0 answers
122 views

Is there a non-bipartite hamiltonian cubic graph on $n$ vertices with no $(n-1)$-cycle?

Is there a cubic (3-regular) graph $G$ on $n$ vertices such that: $G$ is hamiltonian $G$ has no $(n-1)$-cycles $G$ is not bipartite My computer tells me that there are none on up to $24$ vertices.
Gordon Royle's user avatar
  • 12.3k
6 votes
0 answers
134 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 ...
Dmytro Taranovsky's user avatar
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 ...
Agelos's user avatar
  • 1,844
6 votes
0 answers
73 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 ...
EGME's user avatar
  • 1,008
6 votes
0 answers
125 views

Minimum number of hamilton cycles in a 4-connected planar triangulation?

I am currently interested in hamilton cycles (i.e. a cycle through every vertex) in planar triangulations (i.e. planar graphs with every face a triangle). There are non-hamiltonian planar ...
Gordon Royle's user avatar
  • 12.3k
6 votes
0 answers
107 views

Localizing Bondy's metaconjecture on hamiltonicity

Definitions: Let $G$ be a graph on $n$ vertices. $G$ is Hamiltonian provided $G$ has a cycle of length $n$. $G$ is pancyclic provided $G$ has a cycle of length $\ell$ for every $3 \leq \ell \leq n$. ...
D. Ror.'s user avatar
  • 399
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 ...
kabenyuk's user avatar
  • 673
5 votes
0 answers
138 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. ...
M. Winter's user avatar
  • 12.5k
5 votes
0 answers
92 views

Graph gadget related to uniquely hamiltionian regular graphs

A graph is uniquely hamiltonian if it has exactly one hamiltonian cycle. According to a conjecture there are no $r$-regular uniquely hamiltonian graphs for $r > 2$ and of special interest is the ...
joro's user avatar
  • 24.2k
5 votes
0 answers
290 views

A digraph related to permutations

A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence. Consider the following ...
David Feldman's user avatar
4 votes
0 answers
201 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. <...
L.C. Zhang's user avatar
  • 1,605
4 votes
0 answers
206 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 ...
Zach Hunter's user avatar
  • 3,393
4 votes
0 answers
159 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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
4 votes
0 answers
140 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 ...
Manfred Weis's user avatar
  • 12.6k
4 votes
0 answers
95 views

Maximal non-hamiltonian graphs - spanned by a theta graph?

At the moment I am interested in maximal non-hamiltonian graphs, so that is a (simple, undirected) graph that does not itself have a hamilton cycle, but if you add an edge between any two distinct non-...
Gordon Royle's user avatar
  • 12.3k
4 votes
0 answers
65 views

Cage graphs and even cycles

Let $G$ be a $(\nu,g)$-cage graph of degree $\nu$ with girth $g$ and $n=n(\nu,g)$ vertices. Based on the known examples, I am wondering if the following can be proved/disproved: Is it true that ...
Wolfgang's user avatar
  • 13.2k
4 votes
0 answers
250 views

When is an induced subgraph of a Johnson graph hamilton-connected?

The Johnson graph $J(n,k)$ has as its vertices the $k$-subsets of $\{1, 2, \dots, n\}$ where two vertices are adjacent iff their intersection has size $k-1$. A graph is Hamilton-connected if every two ...
jamisans's user avatar
  • 393
3 votes
0 answers
64 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 $...
Agelos's user avatar
  • 1,844
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 ...
Dominic van der Zypen's user avatar
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=...
vidyarthi's user avatar
  • 2,007
3 votes
0 answers
102 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 ...
LeechLattice's user avatar
  • 9,421
3 votes
0 answers
143 views

Hamiltonian cycle polytope for the hypercube graph

Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ ...
Ozzy's user avatar
  • 383
3 votes
0 answers
127 views

Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$). Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$. ...
Felix Goldberg's user avatar
2 votes
0 answers
84 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 ...
ABB's user avatar
  • 3,898
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 ...
joro's user avatar
  • 24.2k
2 votes
0 answers
154 views

Counting Cycle Vertex Covers on Hypercube

Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...
Bill Bradley's user avatar
  • 3,809
2 votes
0 answers
180 views

Details about Kelman's equivalent form of Barnette's conjecture

Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles. Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...
Arnaud Mortier's user avatar
1 vote
0 answers
51 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 ...
whiterock's user avatar
  • 111
1 vote
0 answers
142 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-...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
90 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 ...
Nils Rosehr's user avatar
1 vote
0 answers
139 views

Properties of graphs with Hankel-like adjacency matrix

I am having undirected graphs with adjacency matrices which have a regular Hankel-like form, e.g., $$A=\begin{pmatrix}0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & (6\times 0 \text{ ...
pisoir's user avatar
  • 243
0 votes
0 answers
21 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 ...
L.C. Zhang's user avatar
  • 1,605
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
0 votes
0 answers
56 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]. ...
L.C. Zhang's user avatar
  • 1,605
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
Anđela Todorović's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k