Design of a \(d\)-connected digraph with a minimum number of edges and a quasiminimal diameter. II (Q1917254): Difference between revisions

Let \(n = md + t\) where \(n \geq 2d \geq 6\) and \(0 \leq t < d\). The authors construct a \(d\)-regular and \(d\)-connected digraph \(G(n,d)\) with \(n\) nodes such that the diameter \(D(G(n,d))\) is at most \(\lceil \log_dm \rceil + \lceil t/d \rceil + 1\). In particular, \(D(G (n,d))\) is at most two more than a lower bound for the diameter of such a digraph in general, and at most one more then the lower bound when \(n \leq d^3 + d\). This construction covers some cases not covered in earlier papers. For Part I see ibid. 27, No. 3, 255-265 (1990; Zbl 0707.05027).