Extremal Graphs for a Spectral Inequality on Edge-Disjoint Spanning Trees

Abstract

Liu, Hong, Gu, and Lai proved if the second largest eigenvalue of the adjacency matrix of graph $G$ with minimum degree $\delta \ge 2m+2\ge 4$ satisfies ${\lambda }_2(G)<\delta -\frac{2m+1}{\delta +1}$, then $G$ contains at least $m+1$ edge-disjoint spanning trees, which verified a generalization of a conjecture by Cioabă and Wong. We show this bound is essentially the best possible by constructing $d$-regular graphs ${\mathcal{G}}_{m,d}$ for all $d\ge 2m+2\ge 4$ with at most $m$ edge-disjoint spanning trees and ${\lambda }_2({\mathcal{G}}_{m,d})<d-\frac{2m+1}{d+3}$. As a corollary, we show that a spectral inequality on graph rigidity by Cioabă, Dewar, and Gu is essentially tight.

13 pages, 2 figures