Geodesic
Extremal graphs for a spectral inequality on edge-disjoint spanning trees
Sebastian M. Cioabă1 ; Anthony Ostuni2 ; Davin Park2 ; Sriya Potluri2 ; Tanay Wakhare3 ; Wiseley Wong2
1University of Delaware
2University of Maryland, College Park
3Department of Electrical Engineering and Computer Science, MIT
The electronic journal of combinatorics, Tome 29 (2022) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/10350
Classification : 05C50, 05C35, 05C05
Mots-clés : matrix tree theorem, spanning trees

Sebastian M. Cioabă  1   ; Anthony Ostuni  2   ; Davin Park  2   ; Sriya Potluri  2   ; Tanay Wakhare  3   ; Wiseley Wong  2

1 University of Delaware
2 University of Maryland, College Park
3 Department of Electrical Engineering and Computer Science, MIT 
@article{10_37236_10350,
     author = {Sebastian M. Cioab\u{a} and Anthony Ostuni and Davin Park and Sriya Potluri and Tanay Wakhare and Wiseley Wong},
     title = {Extremal graphs for a spectral inequality on edge-disjoint spanning trees},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {2},
     doi = {10.37236/10350},
     zbl = {1492.05086},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10350/}
}
TY  - JOUR
AU  - Sebastian M. Cioabă
AU  - Anthony Ostuni
AU  - Davin Park
AU  - Sriya Potluri
AU  - Tanay Wakhare
AU  - Wiseley Wong
TI  - Extremal graphs for a spectral inequality on edge-disjoint spanning trees
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10350/
DO  - 10.37236/10350
ID  - 10_37236_10350
ER  - 
%0 Journal Article
%A Sebastian M. Cioabă
%A Anthony Ostuni
%A Davin Park
%A Sriya Potluri
%A Tanay Wakhare
%A Wiseley Wong
%T Extremal graphs for a spectral inequality on edge-disjoint spanning trees
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10350/
%R 10.37236/10350
%F 10_37236_10350
Sebastian M. Cioabă; Anthony Ostuni; Davin Park; Sriya Potluri; Tanay Wakhare; Wiseley Wong. Extremal graphs for a spectral inequality on edge-disjoint spanning trees. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/10350

Cité par Sources :