Enumeration of Paths in Digraphs

Publisher Website
Google Scholar
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.

This publication has 4 references indexed in Scilit: