Premium
Dense bipartite digraphs
Author(s) -
Fiol M. A.,
Yebra J. L. A.
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140608
Subject(s) - bipartite graph , combinatorics , mathematics , upper and lower bounds , degree (music) , order (exchange) , discrete mathematics , graph , physics , mathematical analysis , finance , acoustics , economics
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.