The Number of Euler Tours of Random Directed Graphs
| Autor: | Mary Cryan, Páidí Creed |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
De Bruijn sequence
Applied Mathematics Eulerian path Directed graph Theoretical Computer Science Combinatorics symbols.namesake Computational Theory and Mathematics Euler's formula symbols Discrete Mathematics and Combinatorics Graph (abstract data type) Geometry and Topology BEST theorem Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 20 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/2377 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|