Trace-minimal graphs maximizing the number of spanning trees

Source 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 $K_{d+1}$, which would provide a method to construct large families of $t$-optimal graphs. This conjecture was recently verified for $d\in \{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\geq 3$ and $n\geq 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.