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.

Filter by
Sorted by
Tagged with
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 ...
ABB's user avatar
  • 3,972
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 ...
L.C. Zhang's user avatar
  • 1,615
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 ...
whiterock's user avatar
  • 111
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 ...
Daniel Liu's user avatar
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,027
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,027
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
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) =...
BHT's user avatar
  • 191
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 ...
ABB's user avatar
  • 3,972
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]. ...
L.C. Zhang's user avatar
  • 1,615
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 \...
Dominic van der Zypen's user avatar
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 ...
Jose Antonio Martin H's user avatar
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. <...
L.C. Zhang's user avatar
  • 1,615
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 ...
Dominic van der Zypen's user avatar
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),\\...
vidyarthi's user avatar
  • 2,027
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 ...
chunma's user avatar
  • 21
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 ...
Benjamin Wang's user avatar
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 ...
P.Labarque's user avatar
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 ...
L.C. Zhang's user avatar
  • 1,615
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 $...
Agelos's user avatar
  • 1,854
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
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 ...
Valentin Brimkov's user avatar
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 ...
Dmytro Taranovsky's user avatar
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$ ...
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,027
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 ...
Dominic van der Zypen's user avatar
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. ...
M. Winter's user avatar
  • 12.6k
-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 ...
Dominic van der Zypen's user avatar
-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-...
Dominic van der Zypen's user avatar
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 ...
Sayan Dutta'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,854
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 ...
L.C. Zhang's user avatar
  • 1,615
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 ...
Xin Zhang's user avatar
  • 1,130
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-...
Manfred Weis's user avatar
  • 12.7k
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 ...
Nils Rosehr's user avatar
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 ...
Cyriac Antony's user avatar
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\...
Dominic van der Zypen's user avatar
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.7k
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 ...
Joseph O'Rourke's user avatar
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 ...
Zixun Tau's user avatar
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 ...
Ido314's user avatar
  • 1
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 ...
joro's user avatar
  • 24.2k
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
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 ...
Dominic van der Zypen's user avatar
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 ...
Zach Hunter's user avatar
  • 3,403
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 ...
joro's user avatar
  • 24.2k
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 ...
Zach Hunter's user avatar
  • 3,403
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 ...
EGME's user avatar
  • 1,018
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 ...
Aidan Rocke's user avatar
  • 3,827