2020/05/26 by Márton Borbényi, Borbényi, Márton, Péter Csíkvári +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2005.12752
openalex publication_date 2020/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let F(G) be the number of forests of a graph G. Similarly let C(G) be the number of connected spanning subgraphs of a connected graph G. We bound F(G) and C(G) for regular graphs and for graphs with fixed average degree. Among many other things we study fd=supG∈ GdF(G)1/v(G), where Gd is the family of d--regular graphs, and v(G) denotes the number of vertices of a graph G. We show that f3=23/2, and if (Gn)n is a sequence of 3--regular graphs with length of the shortest cycle tending to infinity, then limn→ ∞F(Gn)1/v(Gn)=23/2. We also improve on the previous best bounds on fd for 4≤ d≤ 9.