Geodesic
Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties
Izvestiya. Mathematics, Tome 77 (2013) no. 6, pp. 1105-1129 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We prove an asymptotic formula for the number of Eulerian circuits in graphs with strong mixing properties and with all vertices having even degrees. This number is determined up to a multiplicative error of the form $O(n^{-1/2+\varepsilon})$, where $n$ is the number of vertices.
Keywords: asymptotic analysis, Gaussian integral, algebraic connectivity
Mots-clés : Eulerian circuit, Laplacian matrix. 
@article{IM2_2013_77_6_a1,
     author = {M. I. Isaev},
     title = {Asymptotic enumeration of {Eulerian} circuits in graphs with strong mixing properties},
     journal = {Izvestiya. Mathematics},
     pages = {1105--1129},
     year = {2013},
     volume = {77},
     number = {6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2013_77_6_a1/}
}
TY  - JOUR
AU  - M. I. Isaev
TI  - Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties
JO  - Izvestiya. Mathematics
PY  - 2013
SP  - 1105
EP  - 1129
VL  - 77
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/IM2_2013_77_6_a1/
LA  - en
ID  - IM2_2013_77_6_a1
ER  - 
%0 Journal Article
%A M. I. Isaev
%T Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties
%J Izvestiya. Mathematics
%D 2013
%P 1105-1129
%V 77
%N 6
%U http://geodesic.mathdoc.fr/item/IM2_2013_77_6_a1/
%G en
%F IM2_2013_77_6_a1
M. I. Isaev. Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties. Izvestiya. Mathematics, Tome 77 (2013) no. 6, pp. 1105-1129. http://geodesic.mathdoc.fr/item/IM2_2013_77_6_a1/

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

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

[3] S. Arora, D. Karger, M. Karpinski, “Polynomial time approximation schemes for dense instances of $NP$-hard problems”, J. Comput. System Sci., 58:1 (1999), 193–210 | DOI | MR | Zbl

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

[5] P. Chebulu, M. Cryan, R. Martin, “Exact counting of Euler tours for generalized series-parallel graphs”, J. Discrete Algorithms, 10 (2012), 110–122 | DOI | MR | Zbl

[6] P. Tetali, S. Vempala, “Random sampling of Euler tours”, Algorithmica, 30:3 (2001), 376–385 | DOI | MR | Zbl

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

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

[9] M. I. Isaev, K. V. Isaeva, “O klasse grafov, obladayuschikh silnymi smeshivayuschimi svoistvami”, Tr. MFTI, 5 (2013), 171–181

[10] M. I. Isaev, “Asymptotic behavior of the number of Eulerian orientations of graphs”, Math. Notes, 93:6 (2013), 816–829 | DOI | DOI | Zbl

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

[12] B. Mohar, “The Laplacian spectrum of graphs”, Graph theory, combinatorics, and applications (Western Michigan University, Kalamazoo, MI, USA, 1988), v. 2, Wiley, New York, 1991, 871–898 | MR | Zbl

[13] 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 (1847), 497–508

[14] W. T. Tutte, “The dissection of equilateral triangles into equilateral triangles”, Proc. Cambridge Philos. Soc., 44:4 (1948), 463–482 | DOI | MR | Zbl