2025/02/09 by Constantine, Gregory P, Magda, Gregory C
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2502.06886
The complexity of a graph is the number of its labeled spanning trees. It is demonstrated that the seven known triangle-free strongly regular graphs, such as the Higman-Sims graph, are graphs of maximal complexity among all graphs of the same order and degree; their complements are shown to be of minimal complexity. A generalization to nearly regular graphs with two distinct eigevalues of the Laplacian is presented. Conjectures and applications of these results to biological problems on neuronal activity are described.