Skip navigation
Skip navigation
A change is coming. Click to see a sneak peek of the new Open Research Repository.

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.

dc.contributor.authorMcKay, Brendan
dc.contributor.authorRobinson, Robert W
dc.date.accessioned2015-12-07T22:17:55Z
dc.identifier.issn0963-5483
dc.identifier.urihttp://hdl.handle.net/1885/18794
dc.description.abstractWe 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.
dc.publisherCambridge University Press
dc.sourceCombinatorics Probability and Computing
dc.titleAsymptotic Enumeration of Eulerian circuits in the Complete Graph
dc.typeJournal article
local.description.notesImported from ARIES
dc.date.issued1998
local.identifier.absfor010104 - Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
local.identifier.ariespublicationu8802668xPUB5
local.type.statusPublished Version
local.contributor.affiliationMcKay, Brendan, College of Engineering and Computer Science, ANU
local.contributor.affiliationRobinson, Robert W, University of Georgia
dc.date.updated2015-12-07T08:15:53Z
local.identifier.scopusID2-s2.0-0542423544
CollectionsANU Research Publications

Download

There are no files associated with this item.
Show simple item record


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

Updated:  17 November 2022/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator