Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-19T22:17:59.824Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Enumeration of Eulerian Circuits in the Complete Graph

Published online by Cambridge University Press:  01 December 1998

BRENDAN D. McKAY  and
ROBERT W. ROBINSON
BRENDAN D. McKAY
Affiliation:
Department of Computer Science, Australian National University, Canberra, ACT 0200, Australia (e-mail: bdm@cs.anu.edu.au)
ROBERT W. ROBINSON
Affiliation:
Department of Computer Science, University of Georgia, Athens, GA 30602-7404, USA (e-mail: rwr@cs.uga.edu)
Get access Rights & Permissions [Opens in a new window]

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−½. 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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 7 , Issue 4 , December 1998 , pp. 437 - 449
Copyright
1998 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)