All Questions
Tagged with graph-theory hamiltonian-paths
45 questions
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 24.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
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
4
votes
1
answer
227
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
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
1
answer
133
views
Constructing optimal Hamilton cycles from optimal Hamilton paths
Question:
can the shortest Hamilton cycle in a complete symmetric graph with weighted edges be constructed from the shortest Hamilton path in the same graph by connecting its ends and then exchanging ...
- 13.2k
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
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
0
votes
1
answer
98
views
Hamiltonian path in the line graph of a connected graph
If $G = (V,E)$ is a finite, connected, simple, undirected graph, is there a Hamiltonian path in the line graph $L(G)$ of $G$?
- 48.9k
1
vote
1
answer
55
views
Hamiltonian path in total graph
Let $G = (V, E)$ be a finite, simple, undirected graph with $V \cap E = \emptyset$. The total graph $T(G)$ is defined on the vertex set $V \cup E$ and its edge set is given by $$E(T(G)) = E \cup \big\{...
- 48.9k
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
1
vote
2
answers
143
views
Does $\{0,1\}^{<\omega}$ have a Hamiltonian path?
Let $\{0,1\}^{<\omega}$ be the collection of $x \in \{0,1\}^\omega$ such that there is $N\in\omega$ with $x(k) = 0$ for all $k\geq N$. We say that $ x, y\in \{0,1\}^{<\omega}$ form an edge if ...
- 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
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
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
-1
votes
2
answers
196
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
4
votes
2
answers
208
views
Hamilton cycles in $\{0,1\}^n$ with fixed Hamming distance
Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d_h(a, b)$ denote the Hamming distance of $a$ and $b$. For $k\in \{1,\ldots,n-1\}$ let $H(n,k)$ be the graph on $\{0,1\}^n$ given by the edge ...
- 48.9k
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
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
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
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
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
2
votes
1
answer
156
views
Directed version of this lemma
On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:
Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
- 71
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
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
4
votes
1
answer
171
views
Hamiltonian paths on the space of graphs
Disclaimer: I am not a professional graph theorist.
Motivation:
Let's consider the set $G_N$ of graphs with $N$ vertices where the vertices are assumed to be distinguishable. This set may ...
- 3,871
5
votes
1
answer
285
views
Integers with a Hamiltonian Square Path
Let $n>1$ be an integer and set $[n]=\{1,\ldots,n\}$. We say that $n$ has a "Hamiltonian Square Path" if there is a bijection $\varphi:[n]\to[n]$ such that for all $k\in [n-1]$ we have that $\...
- 48.9k
6
votes
1
answer
316
views
Are Gray codes in $\{0,1\}^n$ isomorphic?
Let $n\in\mathbb{N}$ be a positive integer. Two elements of $\{0,1\}^n$ form an edge if and only if their Hamming distance equals $1$. It is known that $\{0,1\}^n$ endowed with this graph structure ...
- 48.9k
-1
votes
1
answer
876
views
Find all paths on undirected Graph [closed]
I have an undirected graph and i want to list all possible paths from a starting node.
Each connection between 2 nodes is unique in a listed path is unique, for example give this graph representation:...
2
votes
1
answer
118
views
$\omega$-Hamilton paths in $\mathbb{Z}^n$
For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are ...
- 48.9k
1
vote
1
answer
300
views
Hamiltonian cycles -- Partition function
Assume a complete undirected graph $G'=(\mathcal{V}',\mathcal{E}')$ and the partirion function:
$$\sum_{\boldsymbol{x}\in \{-1,+1\}^n} \prod_{\left(i,j\right)\in \mathcal{E}'} \left[1+x_{i}x_{j}\...
- 153
3
votes
1
answer
1k
views
Tournaments with exactly one directed Hamiltonian path
Every tournament contains a directed Hamiltonian path (a path visiting every vertex exactly once).
Suppose that $T$ is a tournament on $[n]:=\{1,\ldots,n\}$ for some integer $n\geq 2$ with exactly ...
- 48.9k
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
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
882
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
6
votes
1
answer
96
views
Existence of a 2-labelled Hamiltonian Path decomposition of $K_{2n}$
I am trying to see if, for the complete graph $K_{2n}$, there exists a labelling of the vertices with two labels $a$ and $b$ (each used exactly $n$ times), such that we can decompose the graph into $n$...
- 189
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
5
votes
1
answer
423
views
The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$
For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament of order $n.$
Where is $a(n)$ discussed in the literature? Is the exact value ...
- 13.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?
12
votes
1
answer
2k
views
The number of Hamiltonian paths in a tournament
If $h(T)$ denotes the number of (directed) Hamiltonian paths in the tournament $T,$ what is the range of $h(T)$ as $T$ ranges over all (finite) tournaments $T$?
By a classical theorem of Rédei (...
- 13.4k
2
votes
1
answer
1k
views
Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?
Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...
- 241
7
votes
1
answer
517
views
Paths in groups
Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...
- 17.6k
20
votes
6
answers
879
views
Hamiltonian paths where the vertices are integer partitions
I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n.
Let the vertices of the graph G=G(n) denote all the p(n) ...
- 323