The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs

DOI10.1007/BF02128671MaRDI QIDQ805627zbMATH OpenOpenAlexFDO

Authors Brendan D. McKay

Publication date 1990

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02128671

zbMATH Keywords

Eulerian digraphsEulerian oriented digraphsregular tournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Review text

The author determines the asymptotic values of the number of labelled regular tournaments, labelled loop-free simple Eulerian digraphs, and labelled loop-free simple Eulerian oriented digraphs on n vertices, respectively. The last two classes of graphs are also enumerated by their numbers of edges. The method in each case is to identify the required quantity as a coefficient in an n-variable power series, and estimate it by applying the saddle-point method to an appropriate n-dimensional integral.

Recommendations

• scientific article; zbMATH DE number 91021
• scientific article; zbMATH DE number 3877221
• Publication:4351083
• Asymptotic Enumeration of Eulerian Circuits in the Complete Graph
• Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs

Cites work

• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration of tournaments with a given score sequence
• scientific article; zbMATH DE number 3877221 (Why is no real title available?)
• Random regular tournaments

Cited in

(27)

• An upper bound for the number of Eulerian orientations of a regular graph
• Asymptotic enumeration of tournaments with a given score sequence
• Analytic methods in asymptotic enumeration
• A random walk approach to linear statistics in random tournament ensembles
• Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Effective scalar products of D-finite symmetric functions
• Packing triangles in regular tournaments
• Subgraphs of dense random graphs with specified degrees
• Random dense bipartite graphs and directed graphs with specified degrees
• scientific article; zbMATH DE number 3877221 (Why is no real title available?)
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• Asymptotic behavior of the number of Eulerian orientations of graphs
• scientific article; zbMATH DE number 140098 (Why is no real title available?)
• Asymptotic Enumeration of Eulerian Circuits in the Complete Graph
• scientific article; zbMATH DE number 1052843 (Why is no real title available?)
• Packing edge-disjoint triangles in regular and almost regular tournaments
• Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph
• Analytic analysis of algorithms
• On the minimum number of inversions to make a digraph k-(arc-)strong
• A point process on the unit circle with antipodal interactions
• On the degeneracy of spin ice graphs, and its estimate via the Bethe permanent
• On the minimum number of inversions to make a digraph k-(arc-)strong (extended abstract)
• Cumulant expansion for counting Eulerian orientations
• Random walks on Coxeter interchange graphs
• A point process on the unit circle with mirror-type interactions
• Multiplayer rock-paper-scissors

This page was built for publication: The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805627)