# Questions tagged [hamiltonian-paths]

paths on a graph that visit each vertex exactly once

53
questions

0
votes

0
answers

19
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 ...

0
votes

0
answers

50
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.
...

2
votes

2
answers

54
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 \...

2
votes

1
answer

150
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 ...

0
votes

1
answer

72
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$?

1
vote

1
answer

53
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\{...

8
votes

0
answers

423
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 ...

1
vote

0
answers

19
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

106
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

138
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 ...

9
votes

2
answers

1k
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 ...

2
votes

1
answer

87
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$ ...

6
votes

2
answers

289
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 ...

-1
votes

2
answers

126
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 ...

4
votes

2
answers

186
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 ...

6
votes

0
answers

141
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 ...

1
vote

0
answers

139
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&...

13
votes

1
answer

760
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 ...

0
votes

0
answers

142
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$ ...

1
vote

1
answer

102
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
vote

2
answers

149
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\...

1
vote

1
answer

98
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$?

2
votes

1
answer

144
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 ...

1
vote

1
answer

245
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 ...

0
votes

1
answer

110
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 ...

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 ...

2
votes

0
answers

80
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}...

4
votes

1
answer

168
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 ...

5
votes

1
answer

236
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 $\...

2
votes

0
answers

175
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 ...

6
votes

1
answer

307
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 ...

-1
votes

1
answer

715
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

113
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 ...

1
vote

1
answer

148
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 ...

1
vote

1
answer

287
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}\...

1
vote

0
answers

69
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 ...

3
votes

1
answer

746
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 ...

1
vote

0
answers

185
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 $(\...

1
vote

2
answers

292
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{...

1
vote

3
answers

797
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\}$ ...

9
votes

2
answers

1k
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 ...

6
votes

1
answer

91
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$...

1
vote

1
answer

77
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 ...

5
votes

0
answers

89
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 ...

5
votes

1
answer

363
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 ...

3
votes

0
answers

103
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 (...

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 ...

1
vote

1
answer

106
views

### Hamiltonian Path through $n$-bit strings with maximum number of $0\mapsto 1$ transitions

Let $G_n$ be the complete graph whose vertices are the $2^n$ $n$-bit strings. Let $H_n$ denote the Hamiltonian path through $G_n$ that uses the maximum number of edges that correspond to a single bit ...

11
votes

3
answers

1k
views

### Square filling self avoiding walk

I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and ...