On the number of spanning trees in random regular graphs

zbMATH Open1300.05283arXiv1309.6710MaRDI QIDQ405137FDOQ405137

Authors: Catherine Greenhill, Matthew Kwan, David Kofoed Wind 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $dgeq3$ be a fixed integer. We give an asympotic formula for the expected number of spanning trees in a uniformly random $d$-regular graph with $n$ vertices. (The asymptotics are as $noinfty$, restricted to even $n$ if $d$ is odd.) We also obtain the asymptotic distribution of the number of spanning trees in a uniformly random cubic graph, and conjecture that the corresponding result holds for arbitrary (fixed) $d$. Numerical evidence is presented which supports our conjecture.

Full work available at URL: https://arxiv.org/abs/1309.6710

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Spanning trees in random regular uniform hypergraphs
• scientific article; zbMATH DE number 747032
• Spanning trees in random graphs
• The number of spanning trees in regular graphs
• Spanning trees in randomly perturbed graphs
• Distribution of the number of spanning regular subgraphs in random graphs
• Random minimum length spanning trees in regular graphs
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• scientific article; zbMATH DE number 5584928
• The number of spanning trees in some classes of graphs

zbMATH Keywords

spanning treesrandom regular graphssmall subgraph conditioning

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic Enumeration of Spanning Trees
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Title not available (Why is that?)
• Forests, colorings and acyclic orientations of the square lattice
• Title not available (Why is that?)
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The Merino-Welsh conjecture holds for series-parallel graphs
• Title not available (Why is that?)
• On Spanning Trees, Weighted Compositions, Fibonacci Numbers, and Resistor Networks
• Title not available (Why is that?)
• On the number of perfect matchings in random lifts
• The asymptotic number of spanning trees in circulant graphs

Cited In (15)

• Spanning trees in random series-parallel graphs
• Subgraph counts for dense random graphs with specified degrees
• Asymptotic Enumeration of Spanning Trees
• Spanning trees in random regular uniform hypergraphs
• Title not available (Why is that?)
• The average number of spanning trees in sparse graphs with given degrees
• Random tree-weighted graphs
• On large‐girth regular graphs and random processes on trees
• Upper bound for the number of spanning forests of regular graphs
• On spanning structures in random hypergraphs
• Simplicial spanning trees in random Steiner complexes
• Distribution of the number of spanning regular subgraphs in random graphs
• Evaluations of Tutte polynomials of regular graphs
• The number of spanning trees in regular graphs
• The minimum number of spanning trees in regular multigraphs

This page was built for publication: On the number of spanning trees in random regular graphs

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