Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.02548 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914072441651200 |
|---|---|
| author | Romero, Pablo Petingi, Louis |
| author_facet | Romero, Pablo Petingi, Louis |
| contents | A longstanding problem in spectral graph theory asks for graphs with maximum number of spanning trees among all connected simple graphs with a prescribed number of vertices and edges. Such graphs are called t-optimal graphs. Petingi and Rodríguez [Discrete Math. 244 (2002), 351--373] achieved in finding infinitely many t-optimal graphs. Basically, they reduced the problem of finding t-optimal graphs to the determination of almost-regular graphs with minimum number of induced 3-paths.
In this work we revisit the construction of t-optimal graphs given by Petingi and Rodríguez. Then, we generalize the previous construction using the key concept of trace-minimal graph introduced by Ábrego et al. [Linear Algebra Appl. 412 (2006) 161--221]. Finally, as a consequence, we construct infinitely many new t-optimal regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02548 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Construction of infinitely many trace-minimal graphs with maximum number of spanning trees Romero, Pablo Petingi, Louis Combinatorics 05C50 A longstanding problem in spectral graph theory asks for graphs with maximum number of spanning trees among all connected simple graphs with a prescribed number of vertices and edges. Such graphs are called t-optimal graphs. Petingi and Rodríguez [Discrete Math. 244 (2002), 351--373] achieved in finding infinitely many t-optimal graphs. Basically, they reduced the problem of finding t-optimal graphs to the determination of almost-regular graphs with minimum number of induced 3-paths. In this work we revisit the construction of t-optimal graphs given by Petingi and Rodríguez. Then, we generalize the previous construction using the key concept of trace-minimal graph introduced by Ábrego et al. [Linear Algebra Appl. 412 (2006) 161--221]. Finally, as a consequence, we construct infinitely many new t-optimal regular graphs. |
| title | Construction of infinitely many trace-minimal graphs with maximum number of spanning trees |
| topic | Combinatorics 05C50 |
| url | https://arxiv.org/abs/2510.02548 |