The Number of Digraphs with Cycles of Length k

DOI: 10.4236/ojdm.2014.41002   PDF   HTML     2,895 Downloads   4,508 Views  

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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] B. McKay, F. Oggier, G. Royle, N. Sloane, I. Wanless and H. Wilf, “Acyclic Digraphs and Eigenvalues of (0,1)-Matrices,” Journal of Integer Sequences, Vol. 7, 2004, #04.3.3.
[2] D. Cvetkovic, M. Doob and H. Sachs, “Spectra of Graphs,” 3rd Edition, Johann Ambrosius Barth Verlag, Leipzig, 1995.
[3] R. Robinson, “Enumeration of Acyclic Digraphs,” In: R. C. Bose, et al., Eds., Proceedings of 2nd Chapel Hill Conference on Combinatorial Mathematics and Its Applications, Chapel Hill, Orange County, 1970, pp. 391-399.
[4] R. Robinson, “Counting Labeled acyclic Digraphs,” In: F. Harary, Ed., New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 239-273.
[5] R. Stanley, “Acyclic Orientations of Graphs,” Discrete Mathematics, Vol. 5, No. 2, 1973, pp. 171-178.
http://dx.doi.org/10.1016/0012-365X(73)90108-8
[6] E. Bender, L. Richmond, R. Robinson and N. Wormald, “The Asymptotic Number of Acyclic Digraphs (I),” Combinatorica, Vol. 6, No. 1, 1986, pp. 15-22. http://dx.doi.org/10.1007/BF02579404
[7] E. Bender and R. Robinson, “The Asymptotic Number of Acyclic Digraphs (II),” Journal of Combinatorial Theory, Series B, Vol. 44, No. 3, 1988, pp. 363-369. http://dx.doi.org/10.1137/1.9781611971262
[8] I. Gessel, “Counting the Acyclic Digraphs by Sources and Sinks,” Discrete Mathematics, Vol. 160, No. 1-3, 1996, pp. 253-258.
http://dx.doi.org/10.1016/0012-365X(95)00119-H
[9] N. J. Sloane, “The On-Line Encyclopedia of Integers Sequences,” 1996-2003.
[10] A. Berman and R. J. Plemmons, “Nonnegative Matrices in the Mathematical Sciences,” 2nd Edition, Academic, New York, 1994.

  
comments powered by Disqus

Copyright © 2020 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.