3 problems

Regular Boesch conjecture. If an $(n,kn/2)$ UMRG exists and has girth $g$, then it has maximum girth among all $k$-regular $(n,kn/2)$-graphs and, among the $k$-regular $(n,kn/2)$-g…

Cycle-complement conjecture. For any $n\geq 5$ and $e=n(n-3)/2$, the graph

Let $\mathcal C_{n,m}$ be the class of connected simple graphs on $n$ vertices and $m$ edges, and define its corank by $c=m-n+1$. A uniformly most reliable graph (UMRG) is a graph…