All Questions
Tagged with graph-theory hamiltonian-paths
11 questions with no upvoted or accepted answers
8
votes
0
answers
459
views
Extension of Erdős-Gallai (s,t)-path theorem to directed graphs
The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498):
Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every ...
- 81
6
votes
0
answers
218
views
Maximum number of Hamilton paths in a tournament on $n$ vertices
Recall that a tournament is a directed graph $T$ such that for every pair of distinct vertices $\{v,w\}$, exactly one of the ordered pairs $(v,w)$, $(w,v)$ is an arc of $T$.
A tournament is strongly ...
- 12.7k
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
3
votes
0
answers
109
views
Number of Hamiltonian paths in the Hoffman-Singleton graph/Moore graphs?
Does anyone happen to know how many Hamiltonian paths are in the Hoffman-Singleton graph, or have any idea on how I could count such paths?
2
votes
0
answers
111
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
83
views
Zero-One law for Hamiltonian path subgraphs of Hamming Distance Graphs?
$(\alpha,\beta,d)$-Hamming Distance Graph $G_d(\alpha,\beta)$ for $\alpha,\beta\in(0,1]$ is a graph on $2^d$ vertices $v_0,\dots,v_{2^d-1}$ with edges $(v_i,v_j)\in\mathcal E(G_d)$ iff $0<\sum_{t=1}...
- 13.9k
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
338
views
Heuristics for minimum path cover of undirected graph
Suppose you would like to find a set of paths on an undirected connected graph that ensures every vertex is visited exactly once while minimising the number of paths used. In this case, a "path&...
- 139
1
vote
0
answers
186
views
Countable graph that is "as non-traceable as it gets"
If $\omega$ denotes the set of the natural numbers (= the first infinite ordinal), and if $E\subseteq\binom{\omega}{2}$ is any subset, we call a map $f\colon\omega\to\omega$ a walk in the graph $(\...
- 48.9k
0
votes
0
answers
29
views
Explicit Bound in Draganić's Hamiltonicity Result?
Earlier this year, Draganić et al published a remarkable piece of work that resolved Krivelevich and Sudakov's conjecture on the Hamiltonicity of expanders. Here's the abstract:
An n-vertex graph G ...
- 3,979
0
votes
0
answers
97
views
Relation of minimum spanning trees to the shortest Hamiltonian path problem
Spanning trees can be decomposed into a minimal set of maximal path graphs, whose vertices have degree two exactly if they also have degree two in the spanning tree; lets call these paths tree paths.
...
- 13.2k