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 $\mathbf{d}$ is the product of the number of arborescences and the term $\frac{1}{|V|}[\prod_{v\in V}(d_v-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.
@article{10_37236_2377,
author = {P\'aid{\'\i} Creed and Mary Cryan},
title = {The number of {Euler} tours of random directed graphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/2377},
zbl = {1295.05122},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2377/}
}
TY - JOUR
AU - Páidí Creed
AU - Mary Cryan
TI - The number of Euler tours of random directed graphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/2377/
DO - 10.37236/2377
ID - 10_37236_2377
ER -
%0 Journal Article
%A Páidí Creed
%A Mary Cryan
%T The number of Euler tours of random directed graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2377/
%R 10.37236/2377
%F 10_37236_2377
Páidí Creed; Mary Cryan. The number of Euler tours of random directed graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/2377
