Toughness and normalized Laplacian eigenvalues of graphs
作者：
Highlights：
• The toughness of a connected graph G is 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.
• A lower bound for the toughness of a graph in terms of the maximum degree, minimum degree and normalized Laplacian eigenvalues is provided.
• The graphs attaining the two lower bounds regarding toughness and Laplacian eigenvalues given by Gu and Haemers (2022) are characterized.
摘要
•The toughness of a connected graph G is 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.•A lower bound for the toughness of a graph in terms of the maximum degree, minimum degree and normalized Laplacian eigenvalues is provided.•The graphs attaining the two lower bounds regarding toughness and Laplacian eigenvalues given by Gu and Haemers (2022) are characterized.
论文关键词：Toughness,Normalized Laplacian eigenvalue,Algebraic connectivity
论文评审过程：Received 12 November 2021, Revised 2 March 2022, Accepted 5 March 2022, Available online 15 March 2022, Version of Record 15 March 2022.
论文官网地址：https://doi.org/10.1016/j.amc.2022.127075
