On the extreme complexity of certain nearly regular graphs

DOI10.20429/TAG.2026.130101MaRDI QIDQ7237355zbMATH OpenFDO

Authors Gregory P Constantine, Gregory Magda

Publication date 30 April 2026

Published in Theory and Applications of Graphs (Search for Journal in Brave)

Full work available at URL https://doi.org/10.20429/TAG.2026.130101

zbMATH Keywords

complexityeigenvaluelabeled spanning treestree-expander

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

The complexity of a graph is the number of its labeled spanning trees. In this paper, the authors prove that the seven known triangle-free strongly regular graphs 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 eigenvalues of the Laplacian is then presented. Two conjectures and their applications to biological problems in neuronal activity are described.

This page was built for publication: On the extreme complexity of certain nearly regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7237355)