The average number of spanning trees in sparse graphs with given degrees

DOI10.1016/J.EJC.2017.02.003MaRDI QIDQ2357218zbMATH OpenOpenAlexFDO

Authors Catherine Greenhill, M. I. Isaev, Matthew Kwan, Brendan D. McKay

Publication date 19 June 2017

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

spanning trees in a random graph

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Density (toughness, etc.) (05C42)

Abstract: We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence $$, provided that the number of edges is at least $n+extstylefrac12d_{max}^4$, where $d_{max}$ is the maximum degree. A key part of our argument involves establishing a concentration result for a certain family of functions over random trees with given degrees, using Pr"ufer codes.

Recommendations

• The number of spanning trees in graphs with a given degree sequence
• The number of bounded‐degree spanning trees
• On the number of spanning trees in random regular graphs
• Subgraph counts for dense random graphs with specified degrees
• The average number of spanning hypertrees in sparse uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 997340 (Why is no real title available?)
• scientific article; zbMATH DE number 2127722 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 3773632 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (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
• An Electrical Lemma
• Asymptotic Enumeration of Spanning Trees
• Coverings, heat kernels and spanning trees
• Forests, colorings and acyclic orientations of the square lattice
• Martingales on Trees and the Empire Chromatic Number of Random Trees
• On the number of spanning trees in random regular graphs
• Spanning trees in regular graphs
• The number of spanning trees in graphs with a given degree sequence
• The number of spanning trees in regular graphs

Cited in

(15)

• Subgraph counts for dense random graphs with specified degrees
• Metropolized multiscale forest recombination for redistricting
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Anticoncentration for subgraph statistics
• The average number of spanning hypertrees in sparse uniform hypergraphs
• Dirac-type theorems in random hypergraphs
• Random tree-weighted graphs
• The number of bounded‐degree spanning trees
• Embedding clique-factors in graphs with low \(\ell\)-independence number
• Distribution of tree parameters by martingale approach
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
• Transversal Hamilton cycle in hypergraph systems
• F$F$‐factors in Quasi‐random Hypergraphs
• The minimum number of spanning trees in regular multigraphs

This page was built for publication: The average number of spanning trees in sparse graphs with given degrees

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