betaFeedback

WorksMathematics

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 tt-optimal. Petingi and Rodríguez [Discr. Math. 244 (2002), 351-373] reduced the construction of infinitely many tt-optimal graphs to the determination of almost-regular graphs with a minimum number of induced 33-paths, known as almost-regular νν-min graphs. They conjectured that the class of dd-regular νν-min graphs is invariant under the addition or deletion of copies of the complete graph Kd+1K_{d+1}, which would provide a method to construct large families of tt-optimal graphs. This conjecture was recently verified for d∈{1,2,3,4,5}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 dd-regular νν-min graphs on at least nn vertices is invariant under the addition or deletion of copies of Kd+1K_{d+1} whenever d≥3d\geq 3 and n≥d3n\geq d^3. In addition, we introduce a new method to construct tt-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 tt-optimal.

Paper details

vlnc:W_mr7wwjg9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…