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.
104
questions
4
votes
1
answer
152
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
112
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
82
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
83
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
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]. ...
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
103
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
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.
<...
2
votes
1
answer
163
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
192
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
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 $...
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
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 ...
2
votes
1
answer
96
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
294
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
137
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
156
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
93
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
863
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
469
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
113
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
138
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
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 ...
2
votes
1
answer
365
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
168
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
114
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
547
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
277
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
266
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
205
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
103
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
306
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 ...
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 ...
8
votes
3
answers
553
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
138
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 ...