Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs. (English) Zbl 0929.05018

The authors established asymptotic formulas for the number of spanning trees and the number of Eulerian trails in circulant digraphs and in circulant graphs. In particular, if \(T\) is the number of spanning trees and \(E\) is the number of Eulerian trails in any circulant digraph with \(p\) vertices and out-degree \(k\) then it is shown that \({1\over k}[T]^{{1\over p}}\sim 1\) and \({1\over k!}[E]^{{1\over p}}\sim 1\) for \(p\to\infty\). Additional results are established for line graphs and for circulant graphs.


05C05 Trees
05C30 Enumeration in graph theory
05A16 Asymptotic enumeration
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI


[1] Wong, C. K.; Coppersmith, D. A., A combinatorial problem related to multimode memory organization, J. Assoc. Comput., 21, 392-392 (1971) · Zbl 0353.68039
[2] Bermond, J. C., Distributed loop computer networks: A survey, J. Parallel and Distribution Computing, 24, 2-2 (1995) · doi:10.1006/jpdc.1995.1002
[3] Bermond, J. C., Interconnected network, special issue, Discrete Applied Mathematics, 992-992 (1992), Amsterdam: Elsevier Science, Amsterdam · Zbl 0768.90073
[4] Fiol, M. A., Line digraph iteration and the(d, k) digraph problem, IEEE Trans. on Computers, C33, 400-400 (1994) · Zbl 0528.68048
[5] Chen, W. K., Applied Graph Theory (1971), Amsterdam: North-Holland, Amsterdam · Zbl 0229.05107
[6] Zhang, H. S., On the number of spanning trees and Eulerian tours in iterated line digraphs, Discrete Appl. Mathematics, 73, 59-59 (1997) · Zbl 0866.05028 · doi:10.1016/0166-218X(95)00118-B
[7] Cheng, C., Maximizing the number of spanning trees in a graph: Two related problems in graph theory and optimum design theory, J. Combin. Theory., Ser B, 30, 240-240 (1981) · Zbl 0475.05050 · doi:10.1016/S0095-8956(81)80028-7
[8] Lovasz, L.; Plummer, M. D., Matching Theory (1986), Amsterdam: North-Holland, Amsterdam · Zbl 0618.05001
[9] Biggs, N., Algebraic Graph Theory (1985), Amsterdam: North-Holland, Amsterdam
[10] Zhang, F.J., Lin G.N., The complexity of disgraphs, inGraph Theory and Its Applications (ed. Capobianco, M.F.),East and West Annal of New York Academic of Science, 1989, 171-180.
[11] Jacobson, N., Basic Algebra I (1974), San Francisco: W H Freeman and Company, San Francisco · Zbl 0284.16001
[12] Yong, X. R.; Zhang, F. J., An asymptotic property of the number of spanning trees of double fixed stop loop networks, Appl. Math. JCU, 12B, 233-233 (1997) · Zbl 0880.05027
[13] Ablow, C. M.; Brenner, J. L., Roots and canonical forms for circulant matrices, Trans. Amer. Math. Soc., 107, 360-360 (1963) · Zbl 0112.25003 · doi:10.2307/1993900
[14] Imas, M.; Itoh, M., Design to minimize diameter on building networks, IEEE Trans. Computers, C30, 439-439 (1981) · Zbl 0456.94030 · doi:10.1109/TC.1981.1675809
[15] Imas, M.; Itoh, M., A design for directed graph with minimum diameter, IEEE Trans. Computers, C32, 782-782 (1983) · Zbl 0515.94027 · doi:10.1109/TC.1983.1676323
[16] Li, X. L.; Zhang, F. J., On the number of spanning trees and Euler tours in generalized de Brujin graphs, Discrete Mathematics, 94, 189-189 (1991) · Zbl 0746.05029 · doi:10.1016/0012-365X(91)90024-V
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.