Abstract :
Consideration is given to the manner and extent to which propagation delay and terminal packing factors may constrain the interconnection of modules making up large digital network. When formulated in graph-theoretical terms these considerations give rise to the problem of finding linear graphs with a maximum number, n, of nodes for a given degree, d, and diameter, k--a generalization of the problem of finding Moore graphs. A number of inequalities are derived that serve to delimit the function n(d, k), although its precise law of growth remains unknown. Maximal graphs have been found for several cases where Moore graphs are known not to exist. Finally, several interesting techniques are demonstrated for constructing families of graphs, which, though the are usually submaximal, possess a useful regularity of structure.
