Extremal graphs for a spectral inequality on edge-disjoint spanning trees (Q2152797): Difference between revisions

Summary: \textit{Q. Liu} et al. [Linear Algebra Appl. 458, 128--133 (2014; Zbl 1295.05146)] proved if the second largest eigenvalue of the adjacency matrix of graph \(G\) with minimum degree \(\delta \geqslant 2m+2 \geqslant 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 \textit{S. M. Cioabă} and \textit{W. Wong} [ibid. 437, No. 2, 630--647 (2012; Zbl 1242.05056)]. We show this bound is essentially the best possible by constructing \(d\)-regular graphs \(\mathcal{G}_{m, d}\) for all \(d \geqslant 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 \textit{S. M. Cioabă} et al. [Discrete Math. 344, No. 10, Article ID 112527, 9 p. (2021; Zbl 1469.05102)] is essentially tight.