Upper bound for the number of spanning forests of regular graphs

DOI10.1016/J.EJC.2022.103677MaRDI QIDQ2700981zbMATH OpenOpenAlexFDO

Authors Ferenc Bencs, Péter Csikvári

Publication date 27 April 2023

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

Laplacian matricesmatching polynomial

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph polynomials (05C31) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Recommendations

• On the number of forests and connected spanning subgraphs
• The number of bounded‐degree spanning trees
• On the number of spanning trees in random regular graphs
• The number of spanning forests of a graph
• The number of spanning trees in regular graphs

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
• Evaluations of Tutte polynomials of regular graphs
• Exponential growth constants for spanning forests on Archimedean lattices: values and comparisons of upper bounds
• Graph polynomials and their applications. I: The Tutte polynomial
• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Minors in lifts of graphs
• Negative association in uniform forests and connected graphs
• On the computational complexity of the Jones and Tutte polynomials
• On the number of forests and connected spanning subgraphs
• Spanning trees and orientation of graphs
• Spanning trees in regular graphs
• The Tutte polynomial
• Theory of monomer-dimer systems
• Towards a theory of negative dependence.

Cited in

(7)

• The number of spanning forests of a graph
• On the number of forests and connected spanning subgraphs
• Regular graphs with maximum forest number
• Upper bounds for the number of spanning trees of graphs
• The number of spanning trees in regular graphs
• Upper bound for the number of spanning forests of regular graphs
• Cubic graphs and quartic graphs with the minimum number of spanning forests

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: Upper bound for the number of spanning forests of regular graphs

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