Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties

M. I. Isaev

doi:10.1070/IM2013v077n06ABEH002671

Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties

M. I. Isaev

Research output: Contribution to journal › Article › Research › peer-review

1 Citation (Scopus)

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+ε), where n is the number of vertices.

Original language	English
Pages (from-to)	1105-1129
Number of pages	25
Journal	Izvestiya: Mathematics
Volume	77
Issue number	6
DOIs	https://doi.org/10.1070/IM2013v077n06ABEH002671
Publication status	Published - 2013
Externally published	Yes

Keywords

Algebraic connectivity
Asymptotic analysis
Eulerian circuit
Gaussian integral
Laplacian matrix

Access to Document

10.1070/IM2013v077n06ABEH002671

59140290-oaFinal published version, 305 KB

Cite this

@article{11e9c33c59de4ebd9a6917b340533599,

title = "Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties",

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+ε), where n is the number of vertices.",

keywords = "Algebraic connectivity, Asymptotic analysis, Eulerian circuit, Gaussian integral, Laplacian matrix",

author = "Isaev, {M. I.}",

year = "2013",

doi = "10.1070/IM2013v077n06ABEH002671",

language = "English",

volume = "77",

pages = "1105--1129",

journal = "Izvestiya: Mathematics",

issn = "1064-5632",

publisher = "Turpion",

number = "6",

}

TY - JOUR

T1 - Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties

AU - Isaev, M. I.

PY - 2013

Y1 - 2013

N2 - 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+ε), where n is the number of vertices.

AB - 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+ε), where n is the number of vertices.

KW - Algebraic connectivity

KW - Asymptotic analysis

KW - Eulerian circuit

KW - Gaussian integral

KW - Laplacian matrix

UR - http://www.scopus.com/inward/record.url?scp=84891352849&partnerID=8YFLogxK

U2 - 10.1070/IM2013v077n06ABEH002671

DO - 10.1070/IM2013v077n06ABEH002671

M3 - Article

AN - SCOPUS:84891352849

SN - 1064-5632

VL - 77

SP - 1105

EP - 1129

JO - Izvestiya: Mathematics

JF - Izvestiya: Mathematics

IS - 6

ER -

Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties

Abstract

Keywords

Access to Document

Other files and links

Cite this