The number of paths and cycles in a digraph

An algorithm is presented for constructing from the adjacency matrix of a digraph the matrix of its simplen-sequences. In this matrix, thei, j entry,i j, gives the number of paths of lengthn from a pointv_i to a pointv_j; the diagonal entryi, i gives the number of cycles of lengthn containingv_i. The method is then generalized to networks—that is, digraphs in which some value is assigned to each line. With this generalized algorithm it is possible, for a variety of value systems, to calculate the values of the paths and cycles of lengthn in a network and to construct its value matrix of simplen-sequences. The procedures for obtaining the two algorithms make use of properties of a line digraph—that is, a derived digraph whose points and lines represent the lines and adjacency of lines of the given digraph.The research reported here was supported by Grant NSF-G-17771 from the National Science Foundation. We wish to thank Professor Frank Harary for suggesting certain ways of improving an earlier draft of this paper.