The number of Euler tours of a random directed graph

Details The number of Euler tours of a random directed graph The number of Euler tours of a random directed graph

2012-02-10

arxiv.org/abs/1202.2156v1

Computer Science

Discrete Mathematics

Scientific paper

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}{n}[\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.

Affiliated with

Also associated with

No associations

Rating

The number of Euler tours of a random directed graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The number of Euler tours of a random directed graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The number of Euler tours of a random directed graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-274100