Trace-minimal graphs maximizing the number of spanning trees
Abstract
A classical problem in spectral graph theory is to determine, among all simple graphs with a fixed number of vertices and edges, those that maximize the number of spanning trees. Such graphs are called t-optimal. Petingi and Rodríguez [Discr. Math. 244 (2002), 351-373] reduced the construction of infinitely many t-optimal graphs to the determination of almost-regular graphs with a minimum number of induced $3$-paths, known as almost-regular ν-min graphs. They conjectured that the class of d-regular ν-min graphs is invariant under the addition or deletion of copies of the complete graph Kd+1, which would provide a method to construct large families of t-optimal graphs. This conjecture was recently verified for d∈ {1,2,3,4,5} by Gong et al. [Discr. Math. 349(4), 2026]. In this work, we establish an asymptotic version of this conjecture. We prove that the class of d-regular ν-min graphs on at least n vertices is invariant under the addition or deletion of copies of Kd+1 whenever d≥ 3 and n≥ d3. In addition, we introduce a new method to construct t-optimal graphs based on the concept of trace-minimal graphs, originally introduced by Ábrego et al. [Linear Algebra Appl. 412 (2006), 161-221]. As a consequence, we obtain infinitely many graphs that are both trace-minimal and t-optimal.
Related
- Maximizing the number of cliques in Kr+1-free graphs with forbidden properties
- A sharp upper bound on the number of spanning forests of regular graphs
- Maximum number of spanning trees in bipartite graphs with a given diameter
- A Turán-type extremal problem for the number of spanning trees in C4-free graphs
- Wild number for spanning trees in complete and complete bipartite graphs
BibTeX
@misc{romero2026traceminimal,
title = {{Trace-minimal graphs maximizing the number of spanning trees}},
author = {Pablo Romero and Louis Petingi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36127},
eprint = {2610.36127},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36127},
}
RIS
TY - UNPB
TI - Trace-minimal graphs maximizing the number of spanning trees
AU - Pablo Romero
AU - Louis Petingi
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36127
UR - https://arxiv.org/abs/2610.36127
AB - A classical problem in spectral graph theory is to determine, among all simple graphs with a fixed number of vertices and edges, those that maximize the number of spanning trees. Such graphs are called t-optimal. Petingi and Rodríguez [Discr. Math. 244 (2002), 351-373] reduced the construction of infinitely many t-optimal graphs to the determination of almost-regular graphs with a minimum number of induced $3$-paths, known as almost-regular ν-min graphs. They conjectured that the class of d-regular ν-min graphs is invariant under the addition or deletion of copies of the complete graph K_d+1, which would provide a method to construct large families of t-optimal graphs. This conjecture was recently verified for d∈ {1,2,3,4,5} by Gong et al. [Discr. Math. 349(4), 2026]. In this work, we establish an asymptotic version of this conjecture. We prove that the class of d-regular ν-min graphs on at least n vertices is invariant under the addition or deletion of copies of K_d+1 whenever d≥ 3 and n≥ d^3. In addition, we introduce a new method to construct t-optimal graphs based on the concept of trace-minimal graphs, originally introduced by Ábrego et al. [Linear Algebra Appl. 412 (2006), 161-221]. As a consequence, we obtain infinitely many graphs that are both trace-minimal and t-optimal.
ER -