Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Harary, F. and Norman, R. Z. Some properties of line digraphs.Rendiconti del Circolo Mathematico di Palermo, 1960,9, 161–168.
Harary, F., Norman, R. Z., and Cartwright, D.Structural models: An introduction to the theory of directed graphs. New York: Wiley, 1965.
Hasse, Maria. Über die Behandlung graphentheorischer Probleme unter Verwendung der Matrizenrechnung.Wiss. Z. Techn. Univer. Dresden, 1961,10, 1313–1316.
Luce, R. D. and Perry, A. D. A method of matrix analysis of group structure.Psychometrika, 1949,14, 95–116.
Parthasarathy, K. R. Enumeration of paths in digraphs.Psychometrika, 1964,29, 153–165.
Ross, I. C. and Harary, F. On the determination of redundancies in sociometric chains.Psychometrika, 1952,17, 195–208.
Author information
Authors and Affiliations
Additional information
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.
Rights and permissions
About this article
Cite this article
Cartwright, D., Gleason, T.C. The number of paths and cycles in a digraph. Psychometrika 31, 179–199 (1966). https://doi.org/10.1007/BF02289506
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02289506