Geodesic
Asymptotic Behavior of the Number of Eulerian Orientations of Graphs
Matematičeskie zametki, Tome 93 (2013) no. 6, pp. 828-843.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: simple graph, algebraic connectivity, matrix with diagonal dominance, spanning tree, conditioning of a matrix.
Mots-clés : Eulerian orientation of a graph, Laplacian matrix 
@article{MZM_2013_93_6_a3,
     author = {M. I. Isaev},
     title = {Asymptotic {Behavior} of the {Number} of {Eulerian} {Orientations} of {Graphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {828--843},
     publisher = {mathdoc},
     volume = {93},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2013_93_6_a3/}
}
TY  - JOUR
AU  - M. I. Isaev
TI  - Asymptotic Behavior of the Number of Eulerian Orientations of Graphs
JO  - Matematičeskie zametki
PY  - 2013
SP  - 828
EP  - 843
VL  - 93
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2013_93_6_a3/
LA  - ru
ID  - MZM_2013_93_6_a3
ER  - 
%0 Journal Article
%A M. I. Isaev
%T Asymptotic Behavior of the Number of Eulerian Orientations of Graphs
%J Matematičeskie zametki
%D 2013
%P 828-843
%V 93
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2013_93_6_a3/
%G ru
%F MZM_2013_93_6_a3
M. I. Isaev. Asymptotic Behavior of the Number of Eulerian Orientations of Graphs. Matematičeskie zametki, Tome 93 (2013) no. 6, pp. 828-843. http://geodesic.mathdoc.fr/item/MZM_2013_93_6_a3/

[1] B. D. McKay, “The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs”, Combinatorica, 10:4 (1990), 367–377 | DOI | MR | Zbl

[2] M. Mihail, P. Winkler, “On the number of Eulerian orientations of a graph”, Algorithmica, 16:4-5 (1996), 402–414 | MR | Zbl

[3] M. Las Vergnas, “Le polynôme de Martin d'un graphe eulérien”, Ann. Discrete Math., 17 (1983), 397–411 | MR | Zbl

[4] A. Schrijver, “Bounds on the number of Eulerian orientations”, Combinatorica, 3:3-4 (1983), 375–380 | DOI | MR | Zbl

[5] M. Las Vergnas, “An upper bound for the number of Eulerian orientations of a regular graph”, Combinatorica, 10:1 (1990), 61–65 | DOI | MR | Zbl

[6] M. Fiedler, “Algebraic connectivity of graphs”, Czechoslovak Math. J., 23 (98) (1973), 298–305 | MR | Zbl

[7] B. Mohar, “The Laplacian spectrum of graphs”, Graph Theory, Combinatorics, and Applications, Vol. 2, Wiley-Intersci. Publ., John Wiley Sons, New York, 1991, 871–898 | MR | Zbl

[8] 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., 72:12 (1847), 497–508 | DOI

[9] B. D. McKay, R. W. Robinson, “Asymptotic enumeration of eulerian circuits in the complete graph”, Combin. Probab. Comput., 7:4 (1998), 437–449 | MR | Zbl

[10] M. Isaev, “Asymptotic behaviour of the number of Eulerian circuits”, Electron. J. Combin., 18:1 (2011), 219, arXiv: 1104.3046 | MR | Zbl