×
Zhang, Fuji; Yong, Xuerong

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

Sci. China, Ser. A 42, No. 3, 264-271 (1999).
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.
Reviewer: D.P.Brown (Carbondale)

Cited in 12 Documents

MSC:

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

Keywords:

asymptotic formulas; number of spanning trees; number of Eulerian trails; circulant digraphs; circulant graphs; line graphs
PDF BibTeX XML Cite
\textit{F. Zhang} and \textit{X. Yong}, Sci. China, Ser. A 42, No. 3, 264--271 (1999; Zbl 0929.05018)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Wong, C. K., Coppersmith, D. A., A combinatorial problem related to multimode memory organization,J. Assoc. Comput., 1971, 21: 392.
[2] Bermond, J.C., Distributed loop computer networks: A survey,J. Parallel and Distribution Computing, 1995, 24: 2. · Zbl 05480212
[3] Bermond, J.C., Interconnected network, special issue, inDiscrete Applied Mathematics, Amsterdam: Elsevier Science, 1992, 37/38: 992.
[4] Fiol, M. A., Line digraph iteration and the(d, k) digraph problem,IEEE Trans. on Computers, 1994, C33: 400. · Zbl 0528.68048
[5] Chen, W.K.,Applied Graph Theory, Amsterdam: North-Holland, 1971. · Zbl 0229.05107
[6] Zhang, H.S. et al., On the number of spanning trees and Eulerian tours in iterated line digraphs,Discrete Appl. Mathematics, 1997, 73: 59. · Zbl 0866.05028
[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, 1981, 30: 240. · Zbl 0475.05050
[8] Lovasz, L., Plummer, M.D.,Matching Theory, Amsterdam: North-Holland, 1986.
[9] Biggs, N.,Algebraic Graph Theory, Amsterdam: North-Holland, 1985. · Zbl 0284.05101
[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, San Francisco: W H Freeman and Company, 1974. · 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, 1997, 12B: 233. · Zbl 0880.05027
[13] Ablow, C. M., Brenner, J.L., Roots and canonical forms for circulant matrices,Trans. Amer. Math. Soc., 1963, 107: 360. · Zbl 0112.25003
[14] Imas, M., Itoh, M., Design to minimize diameter on building networks,IEEE Trans. Computers, 1981, C30: 439. · Zbl 0456.94030
[15] Imas, M., Itoh, M., A design for directed graph with minimum diameter,IEEE Trans. Computers, 1983, C32: 782. · Zbl 0515.94027
[16] Li, X.L., Zhang, F.J., On the number of spanning trees and Euler tours in generalized de Brujin graphs,Discrete Mathematics, 1991, 94: 189. · Zbl 0746.05029
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.