CLASSIFICATION OF TWO-REGULAR DIGRAPHS WITH MAXIMUM DIAMETER

Abstract

The Klee-Quaife problem is finding 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 find- ing μ(d, c, v) and they also enumerated and classified 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, finding 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.