On the number of spanning trees in random regular graphs

MaRDI QIDQ405137zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1309.6710, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p45

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

zbMATH Keywords

spanning treesrandom regular graphssmall subgraph conditioning

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3878944 (Why is no real title available?)
• scientific article; zbMATH DE number 3773632 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• scientific article; zbMATH DE number 3801587 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic Enumeration of Spanning Trees
• Forests, colorings and acyclic orientations of the square lattice
• On Spanning Trees, Weighted Compositions, Fibonacci Numbers, and Resistor Networks
• On the number of perfect matchings in random lifts
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The Merino-Welsh conjecture holds for series-parallel graphs
• The asymptotic number of spanning trees in circulant graphs

Cited in

(15)

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

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)