Classification of two-regular digraphs with maximum diameter

Abstract

The Klee-Quaife problem is nding the minimum order (d; c; v) of the (d; c; v) graph, which is a c-vertex connected v-regular graph with diameter d. Many authors contributed nding (d; c; v) and they also enumerated and classi ed the graphs in several cases. This problem is naturally extended to the case of digraphs. So we are interested in the extended Klee-Quaife problem. In this paper, we deal with an equivalent problem, nding the maximum diameter of digraphs with given order, focused on 2-regular case. We show that the maximum diameter of strongly connected 2-regular digraphs with order n is n − 3, and classify the digraphs which have diameter n−3. All 15 nonisomorphic extremal digraphs are listed.