Design of a d-connected digraph with a minimum number of edges and a quasiminimal diameter

AbstractTwo fundamental considerations in the design of a communications network are reliability and maximum transmission delay, which can be respectively measured by the connectivity and diameter of a graph representing the network. A d-connected digraph (directed graph) is constructed, which has a minimum number of edges and the diameter is at most one larger than the lower bound for any d and any number of nodes n > d3. It improves upon previous designs, which achieve maximum connectivity with a diameter twice as large as the lower bound