Korean J. Math.  Vol 20, No 2 (2012)  pp.
DOI: https://doi.org/10.11568/kjm.2012.20.2.

CLASSIFICATION OF TWO-REGULAR DIGRAPHS WITH MAXIMUM DIAMETER

Byeong Moon Kim, Byung Chul Song, Woonjae Hwang

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. 


Subject classification



Sponsor(s)



Full Text:

PDF

Refbacks

  • There are currently no refbacks.


ISSN: 1976-8605 (Print), 2288-1433 (Online)

Copyright(c) 2013 By The Kangwon-Kyungki Mathematical Society, Department of Mathematics, Kangwon National University Chuncheon 21341, Korea Fax: +82-33-259-5662 E-mail: kkms@kangwon.ac.kr