TY - JOUR
T1 - Toughness and normalized Laplacian eigenvalues of graphs
AU - Huang, Xueyi
AU - Das, Kinkar Chandra
AU - Zhu, Shunlai
N1 - Publisher Copyright:
© 2022 Elsevier Inc.
PY - 2022/7/15
Y1 - 2022/7/15
N2 - Given a connected graph G, the toughness τG is defined as the minimum value of the ratio |S|/ωG−S, where S ranges over all vertex cut sets of G, and ω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 τ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).
AB - Given a connected graph G, the toughness τG is defined as the minimum value of the ratio |S|/ωG−S, where S ranges over all vertex cut sets of G, and ω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 τ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).
KW - Algebraic connectivity
KW - Normalized Laplacian eigenvalue
KW - Toughness
UR - https://www.scopus.com/pages/publications/85126541562
U2 - 10.1016/j.amc.2022.127075
DO - 10.1016/j.amc.2022.127075
M3 - Article
AN - SCOPUS:85126541562
SN - 0096-3003
VL - 425
JO - Applied Mathematics and Computation
JF - Applied Mathematics and Computation
M1 - 127075
ER -