Toughness and normalized Laplacian eigenvalues of graphs

2023/01/08 by Xueyi Huang, Kinkar Chandra Das, Huang, Xueyi +3
Chemistry · Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Spectral Theory (math.SP) #Synthesis and Properties of Aromatic Compounds

paper · pdf · doi:10.48550/arxiv.2301.02981

openalex publication_date 2023/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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).

Related

• Graph toughness from Laplacian eigenvalues
• Toughness in regular graphs from eigenvalues
• Toughness and spectral radius in graphs
• The spectrum and toughness of regular graphs
• Sufficient conditions for the variation of toughness under the distance spectral in graphs involving minimum degree