Design of a d-connected digraph with a minimum number of edges and a quasiminimal diameter: II Original Research Article

For designing reliable and efficient communications networks, the problem of constructing a maximally connected d-regular digraph (directed graph) with a small diameter is investigated. A maximally connected d-regular digraph with a diameter at most two larger than the lower bound for any number of nodes n ⩾ 2d and any d ⩾ 3 is constructed. Since the diameter of this digraph is quasiminimal (at most one larger than the lower bound) for n ⩽ d3 + d, we can construct maximally connected d-regular digraphs with a quasiminimal diameter for any n (> d) and d, even for those cases not covered in previous papers.