Páidí Creed ; Mary Cryan

The number of Euler tours of a random $d$in/$d$out graph
dmtcs:2787 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

https://doi.org/10.46298/dmtcs.2787
The number of Euler tours of a random $d$in/$d$out graph
Authors: Páidí Creed ^{1}; Mary Cryan ^{2}
NULL##NULL
Páidí Creed;Mary Cryan
1 Department of Computer Science
2 School of Informatics [Edimbourg]
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 \geq 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 AardenneEhrenfest, 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 $[(d1)!]^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.
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)