Minimum order of loop networks of given degree and girth (Q1895819)

Behzad, Chartrand and Wall proposed the conjecture that any regular directed graph of degree \(r\) and girth \(g\) has order \(n\geq r(g- 1)+ 1\). The main result is the following theorem: Let \(X= \text{Cay}(G, S)\) be a connected Abelian Cayley digraph with girth \(g> 3\), degree \(r\), and order \(n\). Then \(n\geq (r+ 1)(g- 1)- 1\) unless \(X\) is a lexicographic product of a family of Cayley digraphs on \(\text{Z}_{n_ i}\), \(1\geq i\geq k\), defined by subsets of the form \(\{x: 1\geq x\geq s_ i\}\), where \(0\geq s_ i\geq n_ i\) and \(n= n_ 1\cdots n_ k\). This bound is best possible.