The number of Euler tours of random directed graphs

zbMath1295.05122MaRDI QIDQ396813

Mary Cryan, Páidí Creed

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p13

zbMATH Keywords

Eulerian graphsrandom regular graphsalgorithms for counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Asymptotic enumeration (05A16) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Euler circuits and DNA sequencing by hybridization
• Almost all cubic graphs are Hamiltonian
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Asymptotic Enumeration of Eulerian Circuits in the Complete Graph
• Almost all regular graphs are hamiltonian
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Two Algorithms for Unranking Arborescences
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Multiplying matrices faster than coppersmith-winograd
• On Unicursal Paths in a Network of Degree 4