TITLE:
The Number of Digraphs with Cycles of Length k
AUTHORS:
Chuanlong Wang, Mudaster Sidik, Xuerong Yong
KEYWORDS:
Acyclic Digraph; Eigenvalue; Power Digraph; (0, 1)-Matrix
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.4 No.1,
January
23,
2014
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 kth
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 nth unit roots [2].