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.
115 questions
1
vote
0
answers
105
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
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\...
- 2,368
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 ...
- 1,444
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 ...
- 1,444
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 ...
- 1,042
12
votes
1
answer
424
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
782
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 ...
- 265
1
vote
2
answers
603
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 ...
- 265
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
16
votes
1
answer
696
views
A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?
Maybe I am missing something, but found potential counterexample to a conjecture
of Nash-Williams.
According to HAMILTONIAN DEGREE SEQUENCES IN DIGRAPHS
The outdegree and indegree sequences of ...
- 1,701
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 ...
- 13.4k
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 ...
CommunityBot
- 1
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 ...
- 196
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
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,486
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
8
votes
3
answers
583
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$ ...
- 61.9k
10
votes
1
answer
513
views
What is the complexity of finding a third Hamilton Cycle in cubic graph?
According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known ...
- 234
14
votes
1
answer
783
views
What was Smith's proof of Smith's theorem on Hamilton cycles in cubic graphs?
In a short 1946 paper "On Hamiltonian Circuits", Tutte proved the famous result that an edge in a cubic graph lies in an even number of Hamilton circuits.
He attributed the result to his friend CAB ...
- 234
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 ...
- 37.7k
14
votes
1
answer
1k
views
Are all cubic graphs almost Hamiltonian?
Call a graph $G$ $n$-almost-Hamiltonian if there is a closed walk in $G$ that visits every vertex of $G$ exactly $n$-times. So a Hamiltonian graph is $n$-almost-Hamiltonian for all $n$. Are all ...
- 211
4
votes
0
answers
160
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 ...
- 15.6k
6
votes
1
answer
335
views
What is the complexity of counting Hamiltonian cycles of a graph?
Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard.
Is it also $PP$-hard in the sense ...
CommunityBot
- 1
9
votes
1
answer
399
views
Are bipartite Moore graphs Hamiltonian?
This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first.
The cycles and complete bipartite graphs ...
CommunityBot
- 1
7
votes
1
answer
210
views
Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)
Many years ago, Grinberg found some uniquely-hamiltonian $3$-connected graphs, and published his results in a paper that has been cited several times as follows.
E. Grinberg, Three-connected graphs ...
- 12.7k
4
votes
0
answers
143
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 ...
- 13.2k
3
votes
0
answers
107
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 ...
- 9,501
6
votes
1
answer
299
views
Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?
In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
- 3,451
4
votes
0
answers
99
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-...
- 12.7k
3
votes
0
answers
145
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$ ...
- 393
4
votes
0
answers
258
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 ...
- 13.4k
1
vote
0
answers
147
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{ ...
- 1
5
votes
1
answer
1k
views
How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?
The question started from a problem brought home by a friend's 5th grader: "How many ways can you seat 5 people around a round table so that the people sitting to the left of any person is different ...
- 32.1k
1
vote
2
answers
321
views
Hamiltonicity and minimal degree in bipartite graphs
Given an integer $k>1$, is there a connected bipartite graph $\Gamma = (A, B, E)$ where $A\cap B = \emptyset$ and $E \subseteq \big\{\{a, b\}:a\in A, b\in B\big\}$ such that
$|A| = |B|$,
$\text{...
- 37.7k
1
vote
3
answers
883
views
Hamiltonian paths in bipartite graphs with 2 sets of "almost" same cardinality
Suppose we have two finite disjoint sets $A, B \neq \emptyset$ such that $|A|$ and $|B|$ differ by at most $1$, and let $\Gamma = (A\cup B, E)$ where $E\subseteq \big\{\{a,b\}: a\in A, b\in B\big\}$ ...
- 13.4k
9
votes
2
answers
2k
views
"Gray code" of all permutations
Informally asking, can we step through all permutations of the set $\{1,\ldots,n\}$ by just using transpositions?
More formally: For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be ...
4
votes
3
answers
506
views
Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?
Consider simple bridgeless cubic planar graphs.
Does each such graph admit a 2-factorization with $\leq 2$ components each of which has even order?
If not, does anyone know of an counterexample?
...
- 6,051
3
votes
2
answers
123
views
Number Associated with Straight-line Drawings of Hamiltonian Graphs
Is there anything known about the maximum number of simple-polygonal Hamilton cycles that a straight-line drawing of a Hamiltonian graph can have?
Put differently, if the vertices of a Hamilton ...
- 151k
11
votes
1
answer
328
views
How many edges can be added to two circles before the graph becomes Hamiltonian?
Start with two $n$-circles $(v_1\cdots v_n)$ and $(w_1\cdots w_n)$ of vertice sets $V$ and $W$, where $n\ge 5$. Add a number of vertex-disjoint edges between $V$ and $W$ (thus no chords) in a way ...
- 13.4k
9
votes
0
answers
245
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: ...
- 12.7k
8
votes
0
answers
123
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.
- 12.7k
6
votes
0
answers
129
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 ...
- 12.7k
1
vote
1
answer
78
views
Graph gadget related to uniquely hamiltionian regular graphs (question #2)
Related to uniquely hamiltionian graphs.
For natural numbers $a,b$ define $(a,b)$ gadget $G$:
$G$ is finite simple graph. Two vertices $u,v$ are of degree $b$
and the rest of the vertices are of ...
CommunityBot
- 1
5
votes
0
answers
99
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 ...
- 25.4k
6
votes
0
answers
76
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 ...
- 13.4k
6
votes
0
answers
108
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$.
...
- 399
0
votes
1
answer
149
views
degG(x) + degG(y) >= n, show that the graph is hamiltonian [closed]
I'm trying to show that a connected graph which has order >=3, and having the following inequality is Hamiltonian:
...
- 7,875