iveXObject('MSXML.XMLHttp'); }, function () { return new ActiveXObject('Microsoft.XMLHTTP'); } ) || null; }, post: function (sUrl, sArgs, bAsync, fCallBack, errmsg) { var xhr2 = this.init(); xhr2.onreadystatechange = function () { if (xhr2.readyState == 4) { if (xhr2.responseText) { if (fCallBack.constructor == Function) { fCallBack(xhr2); } } else { //alert(errmsg); } } }; xhr2.open('POST', encodeURI(sUrl), bAsync); xhr2.setRequestHeader('Content-Length', sArgs.length); xhr2.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded'); xhr2.send(sArgs); }, get: function (sUrl, bAsync, fCallBack, errmsg) { var xhr2 = this.init(); xhr2.onreadystatechange = function () { if (xhr2.readyState == 4) { if (xhr2.responseText) { if (fCallBack.constructor == Function) { fCallBack(xhr2); } } else { alert(errmsg); } } }; xhr2.open('GET', encodeURI(sUrl), bAsync); xhr2.send('Null'); } } function SetSearchLink(item) { var url = "../journal/recordsearchinformation.aspx"; var skid = $(":hidden[id$=HiddenField_SKID]").val(); var args = "skid=" + skid; url = url + "?" + args + "&urllink=" + item; window.setTimeout("showSearchUrl('" + url + "')", 300); } function showSearchUrl(url) { var callback2 = function (xhr2) { } ajax2.get(url, true, callback2, "try"); }
OJDM> Vol.4 No.1, January 2014
Share This Article:
Cite This Paper >>

The Number of Digraphs with Cycles of Length k

Abstract Full-Text HTML Download Download as PDF (Size:102KB) PP. 6-8
DOI: 10.4236/ojdm.2014.41002    2,864 Downloads   4,467 Views  
Author(s)    Leave a comment
Chuanlong Wang, Mudaster Sidik, Xuerong Yong

Affiliation(s)

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.

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

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.

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
OJDM Subscription
E-Mail Alert
OJDM Most popular papers
Publication Ethics & OA Statement
OJDM News
Frequently Asked Questions
Recommend to Peers
Recommend to Library
Contact Us

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.