The number of Euler tours of a random regular graph

Paidi Creed, Mary Cryan

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we obtain the expectation and variance of the number of Euler tours of a random Eulerian directed graph with fixed out-degree sequence. We use this to obtain the asymptotic distribution of the number of Euler tours of a random d-in/d-out graph and prove a concentration result. We are then able to show that a very simple approach for uniform sampling or approximately counting Euler tours yields algorithms running in expected polynomial time for almost every d-in/d-out graph. We make use of the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, which shows that the number of Euler tours of an Eulerian directed graph with out-degree sequence d is the product of the number of arborescences and the term 1|V|[∏v∈V(dv−1)!]. Therefore most of our effort is towards estimating the moments of the number of arborescences of a random graph with fixed out-degree sequence.
Original languageEnglish
Article numberP13
Pages (from-to)1-31
Number of pages31
JournalElectronic Journal of Combinatorics
Volume20
Issue number3
Publication statusPublished - 2013

Keywords

  • Random regular graphs
  • Eulerian graphs
  • Algorithms for Counting

Fingerprint

Dive into the research topics of 'The number of Euler tours of a random regular graph'. Together they form a unique fingerprint.

Cite this