All Questions
Tagged with hamiltonian-graphs graph-theory
102 questions
4
votes
0
answers
69
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 1,851
5
votes
1
answer
271
views
Approximation of Hamiltonian cycles
Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
- 53
0
votes
0
answers
86
views
Uniqueness of compatible cycle decomposition for Eulerian trail
Fleischner mentions in his article Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs about the uniqueness of compatible cycle decomposition that ...
1
vote
0
answers
65
views
Has there been progress on Hamiltonicity in 4-connected claw-free graphs with a constant maximum degree?
In 1984, Matthews and Sumner [1] conjectured that every 4-connected claw-free graph is Hamiltonian, and this conjecture is still wide open.
I would like to know if there has been any progress on this ...
- 1,851
1
vote
0
answers
93
views
15-game graph contains a Hamiltonian path ? Lovász conjecture for groupoids, loops, quasigroups , etc?
Typically Cayley graphs are defined for groups and generators sets S. But basically one only needs some set S and another set V and partially defined operation SxV->V, then one defines graph with ...
- 24.9k
5
votes
2
answers
191
views
Number of Hamiltonian cycles on 24-cell graph
I asked Wolfram Alpha for the number of Hamiltonian cycles on the 24-cell graph.
https://www.wolframalpha.com/input?i=number+of+hamiltonian+cycles+on+24-cell+graph
It answers 114.9 billion but doesn't ...
- 53
0
votes
0
answers
36
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 ...
- 4,058
0
votes
0
answers
52
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,851
1
vote
0
answers
61
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
228
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 ...
- 43
0
votes
0
answers
62
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 ...
- 2,089
0
votes
0
answers
65
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,089
5
votes
0
answers
127
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
1
vote
1
answer
92
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
112
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 ...
- 4,058
2
votes
2
answers
64
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 \...
- 48.9k
5
votes
1
answer
119
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
234
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,851
3
votes
1
answer
104
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,089
2
votes
2
answers
234
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 ...
- 21
2
votes
1
answer
138
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 ...
- 35
1
vote
1
answer
100
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 ...
- 1,851
3
votes
0
answers
70
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,936
3
votes
0
answers
108
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 ...
- 48.9k
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 ...
- 105
6
votes
0
answers
164
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 ...
- 7,545
2
votes
1
answer
106
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$ ...
- 48.9k
3
votes
0
answers
76
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=...
- 2,089
6
votes
2
answers
304
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 ...
- 48.9k
5
votes
0
answers
154
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.
...
- 13.6k
-1
votes
2
answers
200
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 ...
- 48.9k
-1
votes
1
answer
96
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-...
- 48.9k
13
votes
1
answer
1k
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 ...
- 791
3
votes
2
answers
725
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,851
1
vote
1
answer
120
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,190
2
votes
1
answer
495
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 ...
- 191
1
vote
2
answers
186
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\...
- 48.9k
0
votes
0
answers
125
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
64
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 ...
- 13.2k
8
votes
2
answers
598
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 ...
- 151k
2
votes
1
answer
298
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 ...
- 21
5
votes
1
answer
279
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 ...
- 25.4k
2
votes
0
answers
116
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
...
- 25.4k
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 ...
- 48.9k
4
votes
0
answers
230
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 ...
- 3,499
1
vote
1
answer
178
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 ...
- 25.4k
4
votes
1
answer
109
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 ...
- 3,499
2
votes
1
answer
321
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 ...
- 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 ...
- 3,871
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 ...
- 1,018