Asymptotic enumeration of Eulerian circuits in graphs with strong mixing properties

Research output: Contribution to journalArticleResearchpeer-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 languageEnglish
Pages (from-to)1105-1129
Number of pages25
JournalIzvestiya: Mathematics
Volume77
Issue number6
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Algebraic connectivity
  • Asymptotic analysis
  • Eulerian circuit
  • Gaussian integral
  • Laplacian matrix

Cite this