All Questions
Tagged with co.combinatorics hamiltonian-graphs
18 questions with no upvoted or accepted answers
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
1
vote
0
answers
236
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-...
- 13.2k
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