26 problems

Let $X$ be the Cartesian product of $k$ directed cycles of lengths $m_1,m_2,\ldots,m_k$, where $k\geq 3$ and each $m_i\geq 2$. For vertices $u$ and $v$ of $X$, let $d_X(u,v)$ denot…

Hamiltonian path pattern conjecture. In order for a Hamiltonian path to exist on $I[G]$, it is necessary and sufficient that $I[G]$ satisfy one of the four possible patterns:

Acyclic $(3,4)$-tournament spanning-path conjecture. If $G$ is a $(3,4)$-tournament with no closed walk, then $G$ has a spanning path.

$(3,4)$-tournament spanning-path conjecture. Every $(3,4)$-tournament has a spanning path. That is, $f(n,3,4)=n$.

Let $T$ be a strong tournament of order $n\geq 8$, let $e$ be an arc of $T$, and let $P$ be an oriented path of order $n$. El Sahili's conjecture. The tournament $T-e$ contains $P$…

Buratti-Horak-Rosa conjecture. If

Let $K_n$ be drawn simply in the plane, and let $a,b$ be two vertices. A path is plane if no two of its edges cross. All-pairs Hamiltonian-path conjecture. For every simple drawing…

Let $L$ be a multiset of linear lengths, where $\{1^a,(y-k)^b,y^c\}$ denotes the multiset containing $a$, $b$, and $c$ copies of $1$, $y-k$, and $y$, respectively. A multiset is li…

Let $K_n$ be the complete graph, let $\mathcal{D}$ be a simple drawing of it on $n\ge 2$ vertices, and let $v$ and $w$ be distinct vertices of $\mathcal{D}$. A crossing-free Hamilt…

Traceability conjecture. For every integer $k\geq 2$, every $k$-traceable oriented graph of order at least $2k-1$ is traceable.

Aichholzer–Orthaber–Vogtenhuber's conjecture. For each pair of vertices $s,t$ in a simple drawing of $K_n$, there exists a plane Hamiltonian path from $s$ to $t$.

Let $P$ be a finite sign-balanced poset, and let $\mathcal G(P)$ be the graph whose vertices are the linear extensions of $P$ and whose edges correspond to adjacent switches. Ruske…

Let $G$ be a graph on $n$ vertices. A Hamiltonian path is a path containing every vertex of $G$ exactly once. The game domination number $\gamma_g(G)$ is the number of moves in the…

Extremal alternating-sign conjecture. If $n$ is even, then

Cheng–Kano–Wang conjecture. If $K_{n,n}$ contains a PC 1-path-cycle factor, then $K_{n,n}$ contains a PC Hamilton path.

Finite abelian Cayley-digraph conjecture. The digraph $\mathop{\mathsf{C}\mkern-1mu\overrightarrow{\mathsf{ay}}}(G;a,b)$ has two arc-disjoint hamiltonian paths.

Arc-disjoint hamiltonian paths conjecture. The Cartesian product $C_1\mathbin{\Box}C_2\mathbin{\Box}\cdots\mathbin{\Box}C_r$ has two arc-disjoint hamiltonian paths.

Let $G$ be a graph, and let $r_G$ denote the fraction of pairs of vertices of $G$ that are connected by a Hamiltonian path. Equivalently, if $G$ has order $n$, define … where $G$ i…

Asymptotic odd-cycle-different Hamiltonian paths conjecture. If $k>1$, then the maximal number of pairwise $C_{2k+1}$-different Hamiltonian paths on $n$ vertices is at least

Odd-cycle-different Hamiltonian paths conjecture. If $k>1$ and $n$ is large enough, the maximal number of pairwise $C_{2k+1}$-different Hamiltonian paths on $n$ vertices is equal t…

For each $n$, let $X$ be the number of Hamiltonian paths that are increasing in a uniformly random ordering of the edges of $K_n$. Log-normal limit conjecture. As $n\to\infty$, the…

Hamilton path conjecture. The following implication holds

Let $K_v$ denote the complete graph on $\{0,1,\dots,v-1\}$, and let $\ell(H)$ be the multiset of edge-lengths of a graph $H$, with edge lengths in $K_v$ defined by…

Increasing Hamiltonian path conjecture. With probability tending to $1$ as $n\to\infty$, $K_n$ contains an $f$-increasing Hamiltonian path.

Let $K_v$ be the complete graph on \\{0,1,\ldots,v-1\\\}. For an edge $[x,y]$ of $K_v$, define its length by … and let $\ell(H)$ be the multiset of edge-lengths of a Hamiltonian…