Questions tagged [hamiltonian-paths]
paths on a graph that visit each vertex exactly once
60 questions
1 vote
1 answer
222 views
Is the generating function for triple-turn-avoiding grid Hamiltonian paths D-finite?
Let $$ \mathcal{G}_{k,n}:=\{1,\dots ,k\}\times\{1,\dots ,n\}\subset\mathbb{Z}^{2}, \qquad k,n\ge1, $$ be a $k\times n$ rectangular lattice graph. A Hamiltonian path (a walk that visits every vertex ...
0 votes
0 answers
56 views
$k$-th power of spanning tree
I note that there are many papers which study $k$-th power of Hamilton cycle or path. But there is no paper about $k$-th power of spanning tree with bounded degree (spanning tree with bounded degree ...
- 111
2 votes
0 answers
78 views
Longest TSP in the unitary disc
I have the unitary disc $D=\{(x,y) \in R^2: x^2 + y^2 \leq 1\} $, and an integer $n \geq 2$. I want to select $n$ points in $D$ to maximise the length shortest path that connects them all. In other ...
3 votes
1 answer
233 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: ...
- 26.3k
2 votes
0 answers
140 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 ...
- 26.3k
4 votes
1 answer
304 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
190 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,140
2 votes
1 answer
207 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 ...
- 14k
0 votes
0 answers
172 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. ...
- 14k
2 votes
2 answers
107 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 \...
- 53.7k
2 votes
1 answer
211 views
Inspired by a card game: finding a path through $[\mathbb{N}]^n$
Motivation. Today my sons played a card game, in which a fixed number $n$ of cards was lying on the table. A move consists of adding an unused card to the cards on the table, and removing a card from ...
- 53.7k
0 votes
1 answer
131 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$?
- 53.7k
1 vote
1 answer
83 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\{...
- 53.7k
8 votes
1 answer
576 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
1 answer
129 views
Path cover with sets of nodes
I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise ...
0 votes
1 answer
182 views
Traveling salesperson problem algorithm [closed]
I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...
1 vote
2 answers
196 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 ...
- 53.7k
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
161 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$ ...
- 53.7k
6 votes
2 answers
379 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 ...
- 53.7k
-1 votes
2 answers
268 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 ...
- 53.7k
5 votes
2 answers
407 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 ...
- 53.7k
6 votes
0 answers
275 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 ...
- 13.7k
1 vote
0 answers
638 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 ...
- 1,211
0 votes
0 answers
173 views
Number of open tours by a biased rook on a specific $f(n)\times 1$ board which end on a $k$-th cell from the right
We have a simple structure - biased rook of the two types. Biased rook of the first kind which make open tours on a specific $f(n)\times 1$ board where $f(n) = \left\lfloor\log_2{2n}\right\rfloor + 1$ ...
user231922
1 vote
1 answer
174 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,210
1 vote
2 answers
300 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\...
- 53.7k
1 vote
1 answer
177 views
Graph with two edge-disjoint Hamiltonian paths between the same vertex-pair
Provided existence, what is the smallest graph $G(V,E)$ with two edge-disjoint Hamiltonian paths between $u$ and $v;\ \lbrace u,v\rbrace\subset V$?
- 14k
2 votes
1 answer
182 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
1 vote
1 answer
410 views
Algorithm for multiple travelling salesmen problem with given starting point and end point
Given: Set of n>0 cities is to be traversed by m>0 salespeople Where all the salespeople: Are positioned at the same starting city; Finish at a same destination (which different from starting ...
- 11
0 votes
1 answer
144 views
Sources of information on algorithms for finding Hamiltonian cycles (Pósa)
I research various algorithms in complex networks and I am quite new in this field. I am currently focusing on random geometric graphs - Pósa's algorithm for finding a hamiltonian cycle. Can you ...
- 1
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 ...
- 53.7k
2 votes
0 answers
105 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}...
- 1
4 votes
1 answer
212 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 ...
- 4,041
5 votes
1 answer
450 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 $\...
- 53.7k
2 votes
0 answers
226 views
What is the relation between the different generating functions thought as finite approximations of action functionals
In the book Introduction to symplectic topology by MC Duff and Salamon, a discrete analogue of the action functional is defined on $\mathbb{R}^{2n}$. The idea is that a Hamiltonian isotopy can be ...
- 1,237
6 votes
1 answer
361 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 ...
- 53.7k
-1 votes
1 answer
926 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
150 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 ...
- 53.7k
1 vote
1 answer
195 views
Sub-circle-free Christmas-gift-giving
Suppose there is a group of $n$ people giving gifts to one another. Everybody brings a gift but we want the gifts to be "well-distributed" in the group. By this I mean the following: In how many ...
- 196
1 vote
1 answer
346 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
1 vote
0 answers
96 views
Reintegration Method for Shadow Removal
I'm not sure if this is an appropriate question for stack overflow or for math overflow, so please point me in the right direction if I'm in the wrong place. I am trying to implement shadow removal ...
- 119
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 ...
- 53.7k
1 vote
0 answers
228 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 $(\...
- 53.7k
1 vote
2 answers
392 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{...
- 53.7k
1 vote
3 answers
958 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\}$ ...
- 53.7k
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 ...
- 53.7k
6 votes
1 answer
143 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
106 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.7k