The Number of Digraphs with Cycles of Length k

Chuanlong Wang, Mudaster Sidik, Xuerong Yong

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.

DOI: 10.4236/ojdm.2014.41002                

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

Keywords

Acyclic Digraph; Eigenvalue; Power Digraph; (0, 1)-Matrix

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.