Geodesic
Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 40-58.

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

We prove an asymptotic formula for the number of Eulerian orientations for graphs with strong mixing properties and with vertices having even degrees. The exact value is determined up to the multiplicative error $O(n^{1+\varepsilon})$, where $n$ is the number of vertices. Bibliogr. 14.
Mots-clés : Eulerian orientation
Keywords: asymptotic analysis, Gaussian integral, algebraic connectivity, Laplacian. 
@article{DA_2013_20_6_a3,
     author = {M. I. Isaev and K. V. Isaeva},
     title = {Asymptotic enumeration of {Eulerian} orientations for graphs with strong mixing properties},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {40--58},
     publisher = {mathdoc},
     volume = {20},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_6_a3/}
}
TY  - JOUR
AU  - M. I. Isaev
AU  - K. V. Isaeva
TI  - Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 40
EP  - 58
VL  - 20
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_6_a3/
LA  - ru
ID  - DA_2013_20_6_a3
ER  - 
%0 Journal Article
%A M. I. Isaev
%A K. V. Isaeva
%T Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 40-58
%V 20
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_6_a3/
%G ru
%F DA_2013_20_6_a3
M. I. Isaev; K. V. Isaeva. Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 40-58. http://geodesic.mathdoc.fr/item/DA_2013_20_6_a3/

[1] Isaev M. I., “Asimptoticheskoe povedenie chisla eilerovykh orientatsii v grafakh”, Mat. zametki, 93:6 (2013), 828–843 | DOI | Zbl

[2] Biggs N. L., Lloyd E. K., Wilson R. J., Graph theory, Clarendon Press, Oxford, 1976, 1736–1936 | MR

[3] Brightwell G., Winkler P., “Note on counting Eulerian circuits”, Proc. 7th ALENEX and 2nd ANALCO, 2005, 259–262; arXiv: cs/0405067v1

[4] Chung F., “Spectral graph theory”, CBMS Regional Conf. Ser. Math., 92, AMS, New York, 1997, 207 pp. | MR | Zbl

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

[6] I. R. E. Trans. Circuit Theory, CT-5, 4 (1958), 4–7 | DOI

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

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

[9] Lovasz L., “Random walks on graphs: a survey”, Combinatorics, Paul Erdös is eighty, v. 2, Janos Bolyai Math. Soc., Budapest, 1996, 353–397 | MR | Zbl

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

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

[12] Mohar B., “Isoperimetric numbers of graphs”, J. Comb. Theory. Ser. B, 47:3 (1989), 274–291 | DOI | MR | Zbl

[13] Mohar B., “The Laplacian spectrum of graphs”, Graph theory, combinatorics, and applications, v. 2, 1991, 871–898 | MR | Zbl

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