All Questions
Tagged with hamiltonian-graphs graph-theory
102 questions
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 ...
- 1,018
1
vote
3
answers
6k
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 ...
- 475
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 ...
- 5,349
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 ...
- 221
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 ...
- 121
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 ...
- 155
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 ...
- 9,501
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
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{ ...
- 243
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{...
- 48.9k
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\}$ ...
- 48.9k
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 ...
- 48.9k
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 ...
- 12.7k
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?
...
- 443
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 ...
- 13.2k
3
votes
1
answer
234
views
Counting cycle vertex covers on hypercube
Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...
- 3,979
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 ...
- 25.4k
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
15
votes
2
answers
2k
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.7k
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:
...
- 3
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
3
votes
1
answer
266
views
What is the densest bipartite graph with unique Hamiltonian cycle?
In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.
Analogously, what is the ...
- 13.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 ...
user39815
2
votes
1
answer
606
views
Simple decomposition of $K_{2n}-I$ into hamiltonian cycles
http://mathworld.wolfram.com/HamiltonDecomposition.html
In the 1890s, Walecki showed that complete graphs K_n admit a Hamilton decomposition for odd n, and decompositions into Hamiltonian cycles ...
- 400
7
votes
1
answer
736
views
Refinement of Dirac's theorem on Hamiltonian graphs
Dirac's theorem states that if degree of each vertex of a graph $G=(V,E)$ is not less than $|V|/2$, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I ...
- 109k
4
votes
2
answers
349
views
Can we find 3 disjoint directed Hamiltonian cycles in the cube?
Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.
Can we partition the edges of $D$ into $d$ ...
- 19.1k
5
votes
0
answers
295
views
A digraph related to permutations
A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence.
Consider the following ...
- 17.6k
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 ...
- 2,205
3
votes
1
answer
117
views
Hamiltonicity of random graphs with high girth
We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll F$...
- 221
8
votes
2
answers
2k
views
How to efficiently find a Hamiltonian cycle in a graph whose closure is complete?
A graph whose closure is the complete graph is Hamiltonian by the Bondy-Chvátal theorem, but I haven't found a polynomial algorithm for finding a Hamiltonian cycle in such a graph. Is there one that ...
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 ...
- 393
6
votes
1
answer
243
views
Hamiltonicity criteria for sparse graphs
Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).
There are three main classes of criteria for Hamiltonicity that I am aware of:
Dirac-...
- 6,962
3
votes
1
answer
219
views
Regular graphs with $a$ and $b$ Hamiltonian edges
Special case of this question.
Let $G$ be $r$-regular Hamiltonian graph.
An $a$ edge is an edge which is on every Hamiltonian cycle.
A $b$ edge is an edge which is on no Hamiltonian cycle.
$a(G)$ ...
- 25.4k
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 ...
- 13.4k
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 ...
- 2,993
4
votes
1
answer
724
views
Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph
It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard.
By Smith's theorem, ...
- 2,993
0
votes
1
answer
1k
views
Does this graph contain at least two Hamiltonian cycles?
Let $G$ be a simple graph which is a $2n$-cycle together with $n$ chords such that $G$ is $3$-regular. In other words, the set of $n$ chords is a perfect matching of $G$.
I conjecture that for every ...
- 421
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 ...
- 6,962
5
votes
1
answer
224
views
Reconstructing the number of Hamiltonian cycles
As is common terminology in graph reconstruction, given a graph $G$, we call a vertex deleted subgraph of $G$, a card, and call the multiset of all cards, the deck of $G$. The graph reconstruction ...
- 85.6k
2
votes
0
answers
184
views
Details about Kelman's equivalent form of Barnette's conjecture
Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.
Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...
- 1,005
3
votes
0
answers
129
views
Effect of removing a Hamiltonian cycle on the Laplacian spectrum
Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...
- 6,962
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 ...
- 121