# Questions tagged [hamiltonian-paths]

The tag has no usage guidance.

27 questions
Filter by
Sorted by
Tagged with
67 views

66 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 ...
241 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 ...
238 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:...
102 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 ...
98 views

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 ...
248 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}\...
52 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 ...
408 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 ...
176 views

335 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\}$ ...
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 ...
79 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$...
65 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 ...
80 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 ...
217 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 ...
85 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?
1k 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 [...
646 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 ...
86 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 ...
898 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 ...
593 views

### How many ways can a snake lie?

This is essentially a question about counting nonintersecting short paths in a cubic lattice, but with a twist. (One constraint that I did not make clear below is that when to turn is already chosen:...
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 ...