Open Journal of Discrete Mathematics

Volume 4, Issue 1 (January 2014)

ISSN Print: 2161-7635   ISSN Online: 2161-7643

Google-based Impact Factor: 0.64  Citations  

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,261 Downloads   5,243 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:

Wang, C. , Sidik, M. and Yong, X. (2014) The Number of Digraphs with Cycles of Length k. Open Journal of Discrete Mathematics, 4, 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.