We raise the conjecture that for every integer g ≥ 3 there are only finitely many 3-regular digraphs of girth g without vertex disjoint directed cycles of different lengths and give support for this conjecture by proving that it is true for g = 3 .
A ( k , g ) -graph is a k -regular graph with girth g and a ( k , g ) -cage is a ( k , g ) -graph with the fewest possible number of vertices. The cage problem consists of constructing ( k , g ) -graphs of minimum order n ( k , g ) . We focus on girth g = 5 , where cages are known only for degrees k ≤ 7 . We construct ( k , 5 ) -graphs using techniques exposed by Funk (2009)...
Financed by the National Centre for Research and Development under grant No. SP/I/1/77065/10 by the strategic scientific research and experimental development program:
SYNAT - “Interdisciplinary System for Interactive Scientific and Scientific-Technical Information”.