The Number of Digraphs with Cycles of Length k

HTML  Download Download as PDF (Size: 102KB)  PP. 6-8  
DOI: 10.4236/ojdm.2014.41002    3,254 Downloads   5,224 Views  Citations

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].

Share and Cite:

C. Wang, M. Sidik and X. Yong, "The Number of Digraphs with Cycles of Length k," Open Journal of Discrete Mathematics, Vol. 4 No. 1, 2014, pp. 6-8. doi: 10.4236/ojdm.2014.41002.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.