Skip navigation
Skip navigation

Asymptotic Enumeration of Eulerian circuits in the Complete Graph

McKay, Brendan; Robinson, Robert W


We determine the asymptotic behaviour of the number of Eulerian circuits in a complete graph of odd order. One corollary of our result is the following. If a maximum random walk, constrained to use each edge at most once, is taken on Kn, then the probability that all the edges are eventually used is asymptotic to e3/4n-1/2. Some similar results are obtained about Eulerian circuits and spanning trees in random regular tournaments. We also give exact values for up to 21 nodes.

CollectionsANU Research Publications
Date published: 1998
Type: Journal article
Source: Combinatorics Probability and Computing


There are no files associated with this item.

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator