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 ...
- 3,972
13
votes
1
answer
904
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 ...
- 1
1
vote
3
answers
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 ...
- 78.3k
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an ...
- 4,618
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,615
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 ...
CommunityBot
- 1
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 ...
- 111
4
votes
1
answer
168
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 ...
- 3,413
0
votes
0
answers
49
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 ...
- 11.9k
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 ...
- 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 ...
- 673
15
votes
2
answers
1k
views
What is the smallest uniquely hamiltonian graph with minimum degree at least 3?
I would like to know more about uniquely hamiltonian graphs with minimum vertex degree at least 3, and in particular what is the smallest one.
(Recall that a graph is hamiltonian if it has a cycle ...
- 12.3k
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) =...
- 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 ...
- 60.2k
18
votes
1
answer
1k
views
Knight's tours in higher dimensions
I wonder if Knight's Tours have been explored in higher dimensions,
using the following definition of a knight move.
In dimension $d=2$, the knight moves left/right and forward/back
one step and two ...
CommunityBot
- 1
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]. ...
- 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 \...
- 225k
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 ...
- 37.2k
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 ...
- 9,421
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.
<...
- 1,615
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 ...
- 11.4k
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 ...
- 8,076
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),\\...
- 60.2k
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 ...
- 3,413
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 ...
- 37.2k
3
votes
1
answer
499
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,615
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 ...
- 178k
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 $...
- 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 ...
- 45.5k
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 ...
- 229
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 ...
- 6,112
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 ...
CommunityBot
- 1
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$ ...
- 103k
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=...
- 60.2k
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 ...
- 3,964
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.
...
- 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 ...
- 6,571
-1
votes
1
answer
95
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-...
- 740
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 ...
- 1,854
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 ...
- 6,571
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-...
- 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 ...
- 71
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\...
- 1,702
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 ...
- 1,424
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 ...
- 1,424
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 ...
- 1,042
12
votes
1
answer
404
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 ...
CommunityBot
- 1
10
votes
2
answers
759
views
Graphs with many edges avoided by Hamiltonian cycles
Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...
- 255
1
vote
2
answers
582
views
Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity
While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...
- 255