A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs

Let Δ and n be natural numbers such that Δn = 2m is even and Δ ⩽ (2 log n )1/2 - 1. Then as n →, the number of labelled Δ-regular graphs on n vertices is asymptotic to e − λ − λ 2 ( 2 m ) ! m ! 2 m ( Δ ! ) m where λ = (Δ -1)/2. As a consequence of the method we determine the asymptotic distribution of the number of short cycles in graphs with a given degree sequence, and give analogous formulae for hypergraphs.

• Publication year

  1980

• Venue

  European journal of combinatorics (Print)

• Publication date

  1980-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0195-6698(80)80030-8
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Asymptotic Number of Labeled Graphs with Given Degree Sequences

  1978cited by this paper
• The Enumeration of Locally Restricted Graphs (I)

  1959cited by this paper
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen

  1937cited by this paper

• Bringing order to network centrality measures

  2026cites this paper
• Critical time of the almost 2-regular random degree constrained process

  2026cites this paper
• Random walks on edge coloured random graphs

  2026cites this paper
• Inferring signed social networks from contact patterns

  2026cites this paper
• Sharp Square Root Bounds for Edge Eigenvector Universality in Sparse Random Regular Graphs

  2025cites this paper
• Hopping forcing number in random d-regular graphs

  2025cites this paper
• Enumeration of regular multipartite hypergraphs

  2025cites this paper
• Generating Networks to Target Assortativity via Archimedean Copula Graphons

  2025cites this paper
• Learning Mean Field Control on Sparse Graphs

  2025cites this paper
• New Hardness Results for the LOCAL Model via a Simple Self-Reduction

  2025cites this paper
• Asymptotic size of the Karp-Sipser Core in Configuration Model

  2025cites this paper
• Spectrum and local weak convergence of sparse random uniform hypergraphs

  2025cites this paper
• Random graphs, expanding families and the construction of noncompact hyperbolic surfaces with uniform spectral gaps

  2025cites this paper
• Edge-based modelling for disease transmission on random graphs: an application to mitigate a syphilis outbreak

  2025cites this paper
• Dynamics of temporal influence in polarised networks

  2025cites this paper
• On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model

  2025cites this paper
• Self-similarity of communities of the ABCD model

  2025cites this paper
• Rules, agents and order

  2025cites this paper
• Partially Directed Configuration Model with Homophily and Respondent-Driven Sampling

  2025cites this paper
• Block-corrected Modularity for Community Detection

  2025cites this paper
• Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence

  2025cites this paper
• Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching

  2025cites this paper
• An accurate mean-field equation for voter model dynamics on scale-free networks

  2025cites this paper
• Bisection width, max-cut and internal partitions of 5-regular graphs

  2025influential citation
• Who Should be Controlled? The Role of Asymptomatic Individuals, Isolation and Switching in the Dominant Transmission Route in Classical and Network Epidemic Models

  2025cites this paper
• Enhancing Graph Representation Learning with Localized Topological Features

  2025cites this paper
• Multilayer Artificial Benchmark for Community Detection (mABCD)

  2025cites this paper
• Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs

  2025cites this paper
• On the limits of the intervention on complex systems guided by functional networks

  2025cites this paper
• Playing Sudoku on random 3-regular graphs

  2025cites this paper
• Sharp thresholds for NAC-colourings and stable cuts in random graphs

  2025cites this paper
• Connected components in networks with higher-order interactions

  2025cites this paper
• Linear Risk Sharing on Networks

  2025cites this paper
• Rare event probabilities in Random Geometric Graphs

  2025cites this paper
• A construction of random bigraphs and their application to error correction codes

  2025cites this paper
• Percolation on random graphs

  2025cites this paper
• On a characteristic of a conditional distribution of configuration graph

  2025cites this paper
• The Artificial Benchmark for Community Detection with Outliers and Overlapping Communities (ABCD+o2)

  2025cites this paper
• Voter model on heterogeneous directed networks

  2025cites this paper
• Breadth, depth, and flux of course-prerequisite networks

  2025cites this paper
• Sandwiching between random regular graphs and Erd\H{o}s-R\'enyi graphs: configuration model and unions of perfect matchings

  2025cites this paper
• Graphicality of power-law and double power-law degree sequences

  2025cites this paper
• Faithful universal graphs for minor-closed classes

  2025cites this paper
• Data-driven assessment of Apulian road network resilience: Bridge unavailability and inner municipality isolation impact

  2025cites this paper
• EC-SBM synthetic network generator

  2025cites this paper
• Renormalising Feynman diagrams with multi-indices

  2025cites this paper
• A combinatorial approach to nonlinear spectral gaps

  2024cites this paper
• Scale free projections arise from bipartite random networks

  2024cites this paper
• Expectation and Variance of the Degree of a Node in Random Spanning Trees

  2024cites this paper
• Canonical labelling of sparse random graphs

  2024cites this paper
• Hopping Forcing Number in Random $d$-regular Graphs

  2024cites this paper
• The Overlap Gap Property limits limit swapping in QAOA

  2024cites this paper
• Bipartite graphs are $(\frac{4}{5}-\varepsilon) \frac{\Delta}{\log \Delta}$-choosable

  2024cites this paper
• Asymptotic expansion of regular and connected regular graphs

  2024cites this paper
• Polaris: Sampling from the Multigraph Configuration Model with Prescribed Color Assortativity

  2024cites this paper
• Evolution of discordant edges in the voter model on random sparse digraphs

  2024cites this paper
• A note on the singularity probability of random directed d-regular graphs

  2024cites this paper
• Interview with Brendan McKay

  2024cites this paper
• Sequential Stub Matching for Asymptotically Uniform Generation of Directed Graphs with a Given Degree Sequence

  2024cites this paper
• Edge-based Modeling for Disease Transmission on Random Graphs: An Application to Mitigate a Syphilis Outbreak

  2024cites this paper
• The Overlap Gap Property Limits Limit Swapping in the QAOA

  2024cites this paper
• Interaction networks in persistent Lotka-Volterra communities.

  2024cites this paper
• Predicting Feynman periods in ϕ4-theory

  2024cites this paper
• Comparative analysis of graph randomization: Tools,methods, pitfalls, and best practices

  2024cites this paper
• An embedding-based distance for temporal graphs

  2024cites this paper
• First Order Logic of Sparse Graphs with Given Degree Sequences

  2024cites this paper
• First order complexity of finite random structures

  2024cites this paper
• Dense triangle-free $(n, d, \lambda)$-graphs for all orders

  2024cites this paper
• Disease Transmission on Random Graphs Using Edge‐Based Percolation

  2024cites this paper
• Spectral convergence of random regular graphs: Chebyshev polynomials, non‐backtracking walks, and unitary‐color extensions

  2024cites this paper
• Uniformly sampling random directed hypergraphs with fixed degrees

  2024cites this paper
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks

  2024cites this paper
• Hypercurveball algorithm for sampling hypergraphs with fixed degrees

  2024cites this paper
• A Review of Network Models for HIV Spread

  2024cites this paper
• Path decompositions of oriented graphs

  2024cites this paper
• The Spectral Distribution of Random Graphs with Given Degree Sequences

  2024cites this paper
• Small maximal clusters are very unlikely in critical random graphs

  2024cites this paper
• Building a random network with a given expected giant component

  2024cites this paper
• Distribution of the number of cycles in directed and undirected random regular graphs of degree 2.

  2023cites this paper
• The Euler characteristic of the moduli space of graphs

  2023cites this paper
• Artificial benchmark for community detection with outliers (ABCD+o)

  2023cites this paper
• Triangle Processes on Graphs With Given Degree Sequence

  2023cites this paper
• Dynamic Graphs Generators Analysis : an Illustrative Case Study

  2023cites this paper
• Spectral properties of random graphs with fixed equitable partition

  2023cites this paper
• Simple versus nonsimple loops on random regular graphs

  2023influential citation
• Predicting properties of nodes via community-aware features

  2023cites this paper
• The length spectrum of random hyperbolic 3-manifolds

  2023cites this paper
• Dense, irregular, yet always graphic 3-uniform hypergraph degree sequences

  2023cites this paper
• Optimal linear‐Vizing relationships for (total) domination in graphs

  2023cites this paper
• Distribution of shortest path lengths on trees of a given size in subcritical Erdős-Rényi networks.

  2023cites this paper
• On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model

  2023cites this paper
• Self-similarity of Communities of the ABCD Model

  2023cites this paper
• Development Trajectory of Blockchain Platforms: The Role of Multirole

  2023cites this paper
• Meeting, coalescence and consensus time on random directed graphs

  2023cites this paper
• Minors of matroids represented by sparse random matrices over finite fields

  2023influential citation
• Thermodynamics of interacting systems: The role of the topology and collective effects

  2023cites this paper
• Sublinear Time Shortest Path in Expander Graphs

  2023cites this paper
• Graphical realizations of degree sequences, packing multiple colors and random graphs

  2023cites this paper
• Universal ‘winner-takes-it-all’ phenomenon in scale-free random graphs

  2023cites this paper
• A note on the singularity probability of random directed $d$-regular graphs

  2023influential citation