Geodesic
Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties
Izvestiya. Mathematics , Tome 77 (2013) no. 6, pp. 1105-1129.

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

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},
     publisher = {mathdoc},
     volume = {77},
     number = {6},
     year = {2013},
     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
PB  - mathdoc
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
%I mathdoc
%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