Asymptotic Enumeration of Eulerian Circuits in the Complete Graph

Brendan D. Mckay; Robert W. Robinson

doi:10.1017/S0963548398003642

Asymptotic Enumeration of Eulerian Circuits in the Complete Graph

Brendan D. Mckay^*, Robert W. Robinson

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

12 Citations (Scopus)

Abstract

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 K_n, then the probability that all the edges are eventually used is asymptotic to e^3/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.

Original language	English
Pages (from-to)	437-449
Number of pages	13
Journal	Combinatorics Probability and Computing
Volume	7
Issue number	4
DOIs	https://doi.org/10.1017/S0963548398003642
Publication status	Published - 1998

Access to Document

10.1017/S0963548398003642

Cite this

@article{e54ed546f771478281fe6f53e32b73cc,

title = "Asymptotic Enumeration of Eulerian Circuits in the Complete Graph",

abstract = "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.",

author = "Mckay, {Brendan D.} and Robinson, {Robert W.}",

year = "1998",

doi = "10.1017/S0963548398003642",

language = "English",

volume = "7",

pages = "437--449",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Asymptotic Enumeration of Eulerian Circuits in the Complete Graph

AU - Mckay, Brendan D.

AU - Robinson, Robert W.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0542423544&partnerID=8YFLogxK

U2 - 10.1017/S0963548398003642

DO - 10.1017/S0963548398003642

M3 - Article

SN - 0963-5483

VL - 7

SP - 437

EP - 449

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 4

ER -

Asymptotic Enumeration of Eulerian Circuits in the Complete Graph

Abstract

Access to Document

Other files and links

Fingerprint

Cite this