Questions tagged [hamiltonian-paths]

paths on a graph that visit each vertex exactly once

Filter by
Sorted by
Tagged with
0
votes
0answers
62 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
1answer
77 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
2answers
97 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
1answer
42 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$?
0
votes
0answers
53 views

Combinatorial interpretation of poly-Bernoulli numbers of negative index

Here is the comment from Wikipedia: Also it is the number of open tours by a biased rook on a board ${\displaystyle \underbrace {1\cdots 1} _{n}\underbrace {0\cdots 0}_{k}}$ (see A329718 for ...
2
votes
1answer
122 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
1answer
62 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
0answers
18 views

For how many pairs of vertices in 𝐺𝜎,𝑛 we have both (𝑢, 𝑣) ∈ 𝐸𝜎,𝑛 and (𝑣, 𝑢) ∈ 𝐸𝜎,𝑛?

In a De Bruijn Sequence/graph, for how many pairs of vertices in 𝐺𝜎,𝑛 we have both (𝑢, 𝑣) ∈ 𝐸𝜎,𝑛 and (𝑣, 𝑢) ∈ 𝐸𝜎,𝑛? If you can explain me, it will be very nice. Thank you for your help !!
0
votes
1answer
71 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
3answers
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
0answers
74 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
1answer
160 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
1answer
166 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
0answers
132 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
1answer
278 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
1answer
532 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
1answer
103 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
1answer
104 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
1answer
263 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
0answers
61 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
1answer
458 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
0answers
178 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
2answers
232 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
3answers
496 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\}$ ...
8
votes
2answers
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
1answer
84 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
1answer
68 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
0answers
84 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
1answer
254 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
0answers
90 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?
8
votes
1answer
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 [...
2
votes
1answer
921 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
1answer
92 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
3answers
993 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 ...
8
votes
0answers
605 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:...
7
votes
1answer
439 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 ...
16
votes
4answers
645 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(...