Séminaire Lotharingien de Combinatoire, B92d (2026), 13 pp.
Graphs with Few Eigenvalues and an Extreme Number of Spanning Trees
Gregory P. Constantine and Gregory C. Magda
Abstract.
The graphs with which we work have labeled vertices. A problem of theoretical and practical interest is to identify the graphs with n vertices and m edges that have a maximal (or minimal) number of spanning trees. It is demonstrated here that the seven known triangle-free strongly regular
graphs, such as the Higman-Sims graph, are graphs with a
maximum number of spanning trees among all graphs of the
same order and degree; their complements are shown to
have a minimum number of spanning trees. A generalization to almost
regular graphs with two or three distinct eigenvalues of the
Laplacian is then presented.
These results, along with several helpful heuristics, motivate us to formulate conjectures that describe the structure of the graphs having a maximum number of spanning trees in terms of a sieving process involving the traces of the Laplacian.
Received: October 10, 2024.
Revised: February 8, 2026.
Accepted: June 9, 2026.
The following versions are available:
Corrigendum added August 6, 2026, concerning Conjectures 1 and 2 in
the article: