141 problems

A regular tournament is a tournament in which every vertex has the same indegree and outdegree. Kelly's conjecture. Every regular tournament on $n=2k+1$ vertices has a decompositio…

Let $n\geq 2$ be an even integer. A perfect $1$-factorisation of a graph is a partition of its edge set into perfect matchings such that the union of any two distinct perfect match…

Hamiltonicity conjecture. The graph $G(L(P))$ has a Hamiltonian cycle.

Häggkvist's conjecture. If

Hamilton-cycle reconstruction conjecture. There are constants $0\leq c<1$ and $n_0\geq 0$ such that, for all integers $n\geq n_0$, the number of Hamilton cycles of an $n$-vertex gr…

For $\varepsilon>0$, let an $(\varepsilon,d)$-expander be the sublinear-expansion notion used in the source. Hamiltonicity conjecture for regular sublinear expanders. There exists…

Han–Zhao's conjecture. If

Jackson's conjecture. For each $d>2$, every $d$-regular oriented graph on $n\leq 4d+1$ vertices has a Hamilton cycle.

Conjecture on fixed-vertex extensions. For every fixed integer $k$, there exists a polynomial-time algorithm for deciding whether such a digraph has a Hamiltonian cycle.

Let $D$ be a strongly connected digraph on $n$ vertices, with nondecreasing out-degree sequence $d_1^+\leq\cdots\leq d_n^+$ and in-degree sequence $d_1^-\leq\cdots\leq d_n^-$. Nash…

Let $G$ be an $(n+1)$-regular graph on $2n$ vertices. A subset $S\subseteq V(G)$ is called Hamiltonian when the induced subgraph $G[S]$ contains a Hamilton cycle. Erdős–Faudree con…

Let $P_n^k$ be the $k$-th power of the path on $n$ vertices, and let $\deg_G(v)$ denote the degree of $v$ in $G$. Hamiltonicity conjecture for path powers. Let $n\geq4$ and…

Häggkvist's conjecture. Every oriented graph $D$ with

Let $r$ and $n$ be integers with $r\geq 5$ and $n\geq r+3$, and let $G$ be a Hamiltonian $r$-regular graph on $n$ vertices. Haythorpe's conjecture. The graph $G$ has at least … Ham…

Let $G$ be an $(n,d,\lambda)$-graph, meaning an $n$-vertex $d$-regular graph whose non-trivial eigenvalues have absolute value at most $\lambda$. A Hamilton cycle is a cycle contai…

Let $(d_1,d_2,\ldots,d_n)$ be an integer sequence with … where $n>2r$ and $r\geq 3$. A hypergraph is $r$-Hamiltonian if it remains Hamiltonian after the deletion of any set of fewe…

Let $G$ be a $4$-connected planar triangulation on $n$ vertices. The Hakimi–Schmeichel–Thomassen conjecture. $G$ has at least … hamiltonian cycles, with equality if and only if $G$…

Fleischner's dominating circuit conjecture. Every cyclically $4$-edge-connected snark has a dominating circuit.

Let $G$ be an oriented graph, meaning a directed graph with no 2-cycles, on $n$ vertices. Let $\delta^0(G)$ denote its minimum semi-degree, the minimum of its minimum in-degree and…

Let ${\cal H}$ be the set of Hamiltonian cycles in $K_n$. For a family of winning sets ${\cal F}$, let $b_{\cal F}^p$ denote the smallest bias for which Breaker wins the random gam…

Let $P$ be an even simple $3$-polytope, meaning that every facet of $P$ has an even number of vertices. Its vertex-edge graph is the graph whose vertices and edges are those of $P$…

Let $H$ be a red/blue coloured $3$-graph on $n$ vertices, and let $\delta_1(H)$ denote its minimum vertex degree. A loose Hamilton cycle is a cyclic ordering of the vertices in whi…

DeBiasio's conjecture. Every $n$-vertex digraph $D$ satisfying

Let $G$ be a simple graph with $n$ vertices and minimum degree $\delta(G)\geq 3$, and suppose that $G$ contains a Hamiltonian cycle. Girao, Kittipassorn, and Narayanan's conjecture…

For a fixed integer $r\ge 2$, let $K_r$ denote the complete graph on $r$ vertices, and let $\alpha^*(K_r)$ be the minimum-degree threshold of Hamiltonicity for perturbation by a un…