8 problems

Federici's conjecture. The only finite geodetic Cayley graphs are complete graphs and, in the special case of cyclic groups of odd order, an odd cycle.

Let $G$ be a finite group and let $\Sigma$ be a generating set. The undirected Cayley graph $\operatorname{Cay}(G,\Sigma)$ has vertex set $G$ and edges joining $g$ to $ga$ for…

Iršič's conjecture. Determining the strong geodetic number remains ${\cal NP}$-complete on complete multipartite graphs.

Strong geodetic set complexity conjecture. The strong geodetic set problem restricted to complete multipartite graphs is NP-complete.

Approximation conjecture. If $n \leq m \leq \binom{n}{2}$, then $e(m,n)<2$.

Let $G$ be a graph, let $n(G)$ denote its order, and let $G \,\square\, K_2$ be the Cartesian product of $G$ with the complete graph on two vertices. Write $\operatorname{sg}(G)$ f…

Vertex-splitting conjecture. All smallest possible non-diregular $(d,k,+\epsilon)$-digraphs can be derived from a diregular $(d,k)$-geodetic cage by the vertex splitting constructi…

Diregularity conjecture. All geodetic cages are diregular.