Abstract
The class of simple graphs with large algebraic connectivity (the second minimal eigenvalue of the Laplacian matrix) is considered. For graphs of this class, the asymptotic behavior of the number of Eulerian orientations is obtained. New properties of the Laplacian matrix are established, as well as an estimate of the conditioning of matrices with asymptotic diagonal dominance is obtained.
Similar content being viewed by others
References
B. D. McKay, “The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs,” Combinatorica 10(4), 367–377 (1990).
M. Mihail and P. Winkler, “On the number of Eulerian orientations of a graph,” Algorithmica 16(4–5), 402–414 (1996).
M. Las Vergnas, “Le polynôme de Martin d’un graphe eulérien,” Ann. Discrete Math. 17, 397–411 (1983).
A. Schrijver, “Bounds on the number of Eulerian orientations,” Combinatorica 3(3–4), 375–380 (1983).
M. Las Vergnas, “An upper bound for the number of Eulerian orientations of a regular graph,” Combinatorica 10(1), 61–65 (1990).
M. Fiedler, “Algebraic connectivity of graphs,” Czechoslovak Math. J. 23(98), 298–305 (1973).
B. Mohar, “The Laplacian spectrum of graphs,” in Graph Theory, Combinatorics, and Applications, Wiley-Intersci. Publ. (John Wiley & Sons, New York, 1991), Vol. 2, pp. 871–898.
G. Kirchhoff, “Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird,” Ann. Phys. Chem. 148(12), 497–508 (1847).
B. D. McKay and R. W. Robinson, “Asymptotic enumeration Eulerian circuits in the complete graph,” Combin. Probab. Comput. 7(4), 437–449 (1998).
M. Isaev, “Asymptotic behaviour of the number of Eulerian circuits,” Electron. J. Combin. 18(219) (2011).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © M. I. Isaev, 2013, published in Matematicheskie Zametki, 2013, Vol. 93, No. 6, pp. 828–843.
Rights and permissions
About this article
Cite this article
Isaev, M.I. Asymptotic behavior of the number of Eulerian orientations of graphs. Math Notes 93, 816–829 (2013). https://doi.org/10.1134/S0001434613050210
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0001434613050210