The number of Euler tours of a random d-in/d-out graph

Páidí Creed, Mary Cryan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we obtain the expectation and variance of the number of Euler tours of a random d-in/d-out directed graph, for d ≥2. We use this to obtain the asymptotic distribution 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 a d-in/d-out graph is the product of the number of arborescences and the term [(d-1)!]n/n. Therefore most of our effort is towards estimating the asymptotic distribution of the number of arborescences of a random d-in/d-out graph.

Original languageEnglish
Title of host publicationDMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Pages117-128
Number of pages12
Publication statusPublished - 2010

Publication series

NameDiscrete Mathematics & Theoretical Computer Science
ISSN (Electronic)1365-8050

Fingerprint

Dive into the research topics of 'The number of Euler tours of a random d-in/d-out graph'. Together they form a unique fingerprint.

Cite this