Skip navigation
Skip navigation

Asymptotic Enumeration of Eulerian circuits in the Complete Graph

McKay, Brendan; Robinson, Robert W

Description

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
URI: http://hdl.handle.net/1885/18794
Source: Combinatorics Probability and Computing

Download

There are no files associated with this item.


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

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator