Classification of two-regular digraphs with maximum diameter
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (11)
- D. Bhattacharya, "The minimum order of n-connected n-regular graphs with specied diameters", IEEE Trans. Circuits Syst, CAS-32(4), pp.407~409 (1985)
- P. Dankelmann, "The diameter of directed graphs", J. Combin. Theory Ser. B, 94(1), pp.183~186 (2005)
- E. Engelhardt, "Minimum graphs of specied diam- eter, connectivity and valence. II", Discrete Math, 78(3), pp.257~266 (1989)
- B. Grunbaum, "Longest simple paths in polyhedral graphs", J. Lond. Math. Soc, 37, pp.152~160 (1962)
- A. Knyazev, "Diameters of Pseudosymmetric Graphs (Russian)", Mat. Zametki, 41(6), pp.829~843 (1987)
- V. Klee, "Diameters of Polyhedral graphs", Canad. J. Math, 16, pp.602~614 (1964)
- V. Klee, "Classication and enumeration of minimum (d; 3 3)-graphs for odd d", J. Combin. Theory Ser. B, 28, pp.184~207 (1980)
- V. Klee, "Minimum graphs of specied diameter, connectivity and valence", Math. Oper. Res, 1(1), pp.28~31 (1976)
- V. Klee, "Classication and enumeration of minimum (d; 1 3)- graphs and minimum (d; 2 3)-graphs", J. Combin. Theory Ser. B, 23, pp.83~93 (1977)
- J. Moon, "On the diameter of graph", Michigan Math. J, 12, pp.349~351 (1965)
- B. Myers, "The minimum-order three-connected cubic graphs with specied diameters", IEEE Trans. Circuits Syst, CAS-27(8), pp.698~709 (1980)