Dense bipartite digraphs
Miquel Àngel Fiol, J.L.A. Yebra · Journal of Graph Theory · 1990
Abstract For its implications in the design of interconnection networks, it is interesting to find (a) (di)graphs with given maximum (out‐)degree d and diameter D that have large order; (b) (di)graphs of given order and maximum (out‐)degree d that have small diameter. (Di)graphs of either type are often called dense. This paper considers the case of bipartite digraphs. For problem (a) it is shown that a Moore‐like bound on the order of such digraphs can be (and in fact is) attained only when D ≤ 4. For D > 4 a construction is presented that yields a family of bipartite digraphs with order larger than (d4 — 1)/d4 times the above‐mentioned bound. For problem (b) an appropriate lower bound is derived and a construction is presented that provides bipartite digraphs of any (even) order whose diameter does not exceed this lower bound in more than one.