The Number of Digraphs with Cycles of Length *k*

Affiliation(s)

Department of Mathematics, Taiyuan Normal University, Taiyuan, China.

Department of Mathematics, Yili Normal University, Yili, China.

Department of Mathematical Sciences, University of Puerto Rico, Mayaguez, USA.

Department of Mathematics, Taiyuan Normal University, Taiyuan, China.

Department of Mathematics, Yili Normal University, Yili, China.

Department of Mathematical Sciences, University of Puerto Rico, Mayaguez, USA.

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

Cite this paper

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.

C. Wang, M. Sidik and X. Yong, "The Number of Digraphs with Cycles of Length

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.

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