Minimum order of loop networks of given degree and girth

Behzad, Chartrand and Wall proposed the conjecture that any regular digraph of degreer and girthg has ordern r(g – 1) + 1. The conjecture was proved in 3] for vertex transitive graphs. For Loop Networks the conjecture is equivalent to a theorem of Shepherdson in additive number theory. We show that, except for graphs of a particular structure, Loop Networks, and in general Abelian Cayley graphs, verify the stronger inequalityn (r + 1)(g – 1) – 1. This bound is best possible.Supported by the Spanish Research Council (CICYT) under project TIC 90-0712 and Acción Integrada Hispanofrancesa, TIC 79B.