Dense bipartite digraphs

Abstract

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 ( d 4 — 1)/ d 4 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.