Key points are not available for this paper at this time.
Preliminaries. We shall be concerned with finite graphs of t directed lines on n points, or nodes. The lines are joinsfrom one point to another. To each point, Pi, is associated a non-negative number pair (ri, si), where ri is the number of lines from Pi, and si is the number of lines to Pi. These number pairs are considered to be fixed local restrictions. Obviously, ri= Ej sj, =t. The vectors r and s, with elements ri and si, respectively, are two n-part non-negative integer partitions of t, with vanishing parts permitted. In general, it is possible to construct many n-node graphs satisfying a specified set of local restrictions. The main result of this paper gives the number of distinct graphs of this kind. The enumeration is helpful in studying communication networks in which the ith element has ri receivers and si senders; here the pertinent question is whether such graphs exist. In the isomorphic problem in group organization theory, where the ith individual in the group gives information or orders or choices to ri others and receives from si others, the exact number of graphs is needed in order to construct the probability distributions for random variables defined over the graphs. All of these activities, like the graphs, are irreflexive and take values on a twoelement Boolean algebra. Previous work on numbers of graphs has been devoted exclusively to counts of graphs topologically distinct under permutations of the points which preserve joins. Thus, G. Polya 9 gave explicitly the numbers of trees and rooted trees on n points, R. Otter 8 gave simpler purely combinatorial methods for counting trees and rooted trees, and F. Harary and G. E. Uhlenbeck 6 gave the numbers of free pure and mixed Husimi trees. Also, F. Harary indicates in an abstract 5 that Polya's method of generating functions may be extended to give the numbers of ordinary and of directed graphs on n points and t lines. R. L. Davis 3 defines and gives a method for counting the numbers of various subclasses of directed graphs on n points. The problem we face is essentially different from all of these and requires quite different methods of enumeration. We shall make use of certain bipartitional functions due to Cayley
Katz et al. (Sun,) studied this question.