14 problems

Cyclic edge-connectivity conjecture. Every $(k,g)$-cage is cyclically $(k-2)g$-edge-connected.

Let $r\geq 2$ and $g\geq 3$. An $(r,g)$-graph is a finite simple $r$-regular graph of girth $g$, and an $(r,g)$-cage is an $(r,g)$-graph with the minimum possible number of vertice…

Let $k\geq 3$, and let $f(k,g)$ denote the minimum number of vertices in a $k$-regular graph of girth $g$. The quantities satisfy … For all known infinite families of regular graph…

Cubic-cage conjecture. For infinitely many integers $g$, there exists a cubic graph $G$ such that

Cycle-separating cut conjecture. For each $(k,g)$-cage $G$, every cycle-separating edge-cut of size $(k-2)g$ in $G$ separates a $g$-cycle.

Fu et al.'s conjecture. Every simple $(k,g)$-cage is $k$-connected.

Even-girth cage bipartiteness conjecture. Every cage of even girth is bipartite.

Let a $(d,g)$-cage $G$ be a graph of degree $d$ and girth $g$, and let $\operatorname{mp}(G)$ denote its monophonic position number. Thomas's conjecture. For sufficiently large $g$…

A $(3,6,\underline{7})$-graph is a cubic graph of girth 6 with no 7-cycle. Its odd girth is the length of a shortest odd cycle, and the smallest such graph with odd girth 11 has 28…

Let a $(k,g,\underline{g+1})$-graph be a graph of degree $k$ and girth $g$ with no cycle of length $g+1$. The notation $(3,11,\underline{12})$ therefore denotes a cubic graph of gi…

Nonseparating girth-cycle conjecture. Every $g$-cycle in a $(k;g)$-cage is nonseparating.

A $(d,g)$-cage is a graph of minimum possible order among graphs with degree $d$ and girth $g$, and ${\rm mp}(G)$ denotes the monophonic position number of $G$. The cage monophonic…

The cage conjecture. The $(k,5)$-cage is the unique smallest graph with cop number $k$.

Let $r$ and $m$ be integers with $2\le r<m$, and let $n(\{r,m\};6)$ denote the minimum order of a biregular graph with degree set $\{r,m\}$ and girth $6$. Yuansheng–Liang conjectur…