Counting paths

There is an interesting relation between the number of paths in a diagram and the number to be found in the dual diagram. Recall that the elements of powers of the connectivity matrix M represent the number of paths joining the row index node to the column index node; if the respective sums are taken, the total number n of paths results. In matrix form, taking u to be a vector whose components are all ones,

Given that u is an eigenvector (with unit eigenvalue) of a row stochastic matrix just as is a similar eigenvector of a column stochastic matrix, it follows from the RC decomposition of the dual that

Hence ; entirely similar reasoning reveals that

Although the matrices figuring in the equation are not likely to be identical to their duals, they both contain the same number of 1's; in particular the number of paths of length 2 in any diagram is the same as the number of links in its dual diagram. Note that this is a property of directed graphs, not necessarily of general graphs.

Another useful property of duality is the relation between Hamiltonian paths and Eulerian paths. A Hamiltonian path is one which visits each node of the diagram once (clearly, the diagram must be connected), while an Eulerian path is one which traverses every link once (in the proper direction) even though nodes are repeated during the voyage. A Hamiltonian path, one of which is usually hard to find, becomes an Eulerian path in the antidual diagram, criteria for which are generally easier to obtain. The result would be more useful if more graphs actually had antiduals.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx