This article is cited in 1 paper

Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties

M. I. Isaev

Moscow Institute of Physics and Technology

Abstract: 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: Eulerian circuit, asymptotic analysis, Gaussian integral, algebraic connectivity, Laplacian matrix.

UDC: 519.1

MSC: 05C30, 05C45, 41A60

Received: 27.09.2012

DOI: 10.4213/im8052

 English version: Izvestiya: Mathematics, 2013, 77:6, 1105–1129

Bibliographic databases:

• 
• 
• 
• 
• 
• 
•