Back to Search
Start Over
Toughness and normalized Laplacian eigenvalues of graphs
- Publication Year :
- 2023
-
Abstract
- Given a connected graph $G$, the toughness $\tau_G$ is defined as the minimum value of the ratio $|S|/\omega_{G-S}$, where $S$ ranges over all vertex cut sets of $G$, and $\omega_{G-S}$ is the number of connected components in the subgraph $G-S$ obtained by deleting all vertices of $S$ from $G$. In this paper, we provide a lower bound for the toughness $\tau_G$ in terms of the maximum degree, minimum degree and normalized Laplacian eigenvalues of $G$. This can be viewed as a slight generalization of Brouwer's toughness conjecture, which was confirmed by Gu (2021). Furthermore, we give a characterization of those graphs attaining the two lower bounds regarding toughness and Laplacian eigenvalues provided by Gu and Haemers (2022).
- Subjects :
- Mathematics - Combinatorics
Mathematics - Spectral Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2301.02981
- Document Type :
- Working Paper