Skip to Main content Skip to Navigation
Conference papers

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

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 \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 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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185585
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:33:14 PM
Last modification on : Thursday, October 26, 2017 - 4:34:02 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:57:25 AM

File

dmAM0109.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-01185585, version 1

Collections

Citation

Páidí Creed, Mary Cryan. The number of Euler tours of a random $d$-in/$d$-out graph. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.117-128. ⟨hal-01185585⟩

Share

Metrics

Record views

167

Files downloads

728