The Number of Digraphs with Cycles of Length *k*

Show more

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

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.