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) Vertex degrees (05C07) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

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

• 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
• 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?)
• 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

(16)

• The minimum number of spanning trees in regular multigraphs
• Random tree-weighted graphs
• Dirac-type theorems in random hypergraphs
• The average number of spanning hypertrees in sparse uniform hypergraphs
• Anticoncentration for subgraph statistics
• 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
• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
• Distribution of tree parameters by martingale approach
• Embedding clique-factors in graphs with low -independence number
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• The number of bounded‐degree spanning trees
• FF‐factors in Quasi‐random Hypergraphs
• Transversal Hamilton cycle in hypergraph systems
• Improvements on induced subgraphs of given sizes

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)