Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-01-08T10:08:42.770Z Has data issue: false hasContentIssue false
  • English
  • Français

Enumeration of Paths in Digraphs

Published online by Cambridge University Press:  01 January 2025

K. R. Parthasarathy
K. R. Parthasarathy*
Affiliation:
Indian Institute of Technology, Kharagpur, India
Get access Rights & Permissions [Opens in a new window]

Abstract

The solution of the problem of enumeration of the n-paths in a digraph has so far been attempted through an indirect approach of enumerating the redundant chains. The approach has yielded an algorithm for determination of the general formula for the matrix of redundant n-chains and also a partial recurrence formula for the same. This paper presents a direct approach to the problem. It gives a recurrence relation expressing the matrix of n-paths of a digraph in terms of the matrices of (n − 1)-paths of its first-order subgraphs. The result is exploited to give an algorithm for computing the matrix of n-paths. The algorithm is illustrated with a 6 × 6 matrix.

Type
Original Paper
Information
Psychometrika , Volume 29 , Issue 2 , June 1964 , pp. 153 - 165
Copyright
Copyright © 1964 Psychometric Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

The writer wishes to express his indebtedness to Dr. A. K. Gayen of Indian Institute of Technology, Kharagpur, for constant guidance and encouragement. Thanks are also due to Dr. S. N. N. Pandit of the Indian Institute of Technology, Kharagpur, and Shri M. T. Subrahmanya of Indian Statistical Institute, Calcutta, for helpful suggestions.

References

Festinger, L. The analysis of sociograms using matrix algebra. Human Relat., 1949, 2, 153–158.CrossRefGoogle Scholar
Harary, F. Graph theoretic methods in management science. Mgmt Sci., 1959, 4, 387–403.CrossRefGoogle Scholar
Luce, R. D. and Perry, A. D. A method of matrix analysis of group structure. Psychometrika, 1949, 14, 95–116.CrossRefGoogle ScholarPubMed
Ross, I. C. and Harary, F. On the determination of redundancies in sociometric chains. Psychometrika, 1952, 17, 195–208.CrossRefGoogle Scholar