The Number of Digraphs with Cycles of Length <i>k</i>

Abstract

In this note , we show that the number of digraphs with n vertices and with cycles of length k , 0 ≤ k ≤ n , is equal to the number of n × n (0,1) -matrices whose eigenvalues are the collection of copies of the entire k th unit roots plus, possibly, 0’s. In particular, 1) when k = 0 , since the digraphs reduce to be acyclic, our result reduces to the main theorem obtained recently in [ 1 ] stating that, for each n = 1, 2, 3, … , the number of acyclic digraphs is equal to the number of n × n (0,1) -matrices whose eigenvalues are positive real numbers; and 2) when k = n , the digraphs are the Hamiltonian directed cycles and it, therefore, generates another well-known (and trivial) result: the eigenvalues of a Hamiltonian directed cycle with n vertices are the n th unit roots [ 2 ].