Exact anatomy of the BCW circular construction

Definitions and mathematical statement

A finite simple loopless digraph $D$ is $r$-regular if every vertex has both indegree and outdegree exactly $r$. Opposite arcs are allowed. Its directed girth is the length of its shortest directed cycle, with cycle length measured by the number of arcs. For $r\ge1$ a finite $r$-regular digraph has a directed cycle, so this girth is finite. For integers $r\ge1$ and $g\ge2$, let \[ m(r,g)=\min\{|V(D)|:D\text{ is a simple loopless }r\text{-regular digraph of directed girth }g\}. \] The Behzad--Chartrand--Wall conjecture is \[ m(r,g)=r(g-1)+1. \] In particular, every such regular digraph should have at least the specified number of vertices. Both degree conditions hold at each vertex, rather than merely on average.

The matching candidate construction has vertex set $\mathbb Z/N\mathbb Z$, where $N=r(g-1)+1$, and arcs $i\to i+j$ for $j=1,\ldots,r$ modulo $N$. It is $r$-regular and has girth $g$, showing what sharpness means in the conjecture. For a short directed cycle the positive increments would have to sum to a multiple of $N$, which cannot happen in fewer than $g$ steps. The problem is the universal lower bound for arbitrary digraphs, without any cyclic symmetry assumption. The simplicity condition excludes inflating the degree by repeating an arc.

Short English statement

Is r times one less than the girth, plus one, the minimum order of an r-regular directed graph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001035 (AIM-COMBINATORICS-0160), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 4. Original workshop question underlying AIM-COMBINATORICS-0160. https://aimath.org/WWN/caccetta/caccetta.pdf.