2025/10/08 by Ruifang Liu, Liu, Ruifang, Ao Fan +3
Computer Science · Mathematics · #05C35 #05C50 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2510.07007
openalex publication_date 2025/10/08 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
The \it toughness τ(G)=min\(|S|)/(c(G-S)): S~is a vertex cut in~G\ for G\ncong Kn, which was initially proposed by Chvátal in 1973. A graph G is called \it t-tough if τ(G)≥ t. Let λi(G) be the i-th largest eigenvalue of the adjacency matrix of a graph G. In 1996, Brouwer conjectured that τ(G)≥\fracdλ-1 for a connected d-regular graph G, where λ=max\|λ2|, |λn|\. Gu [SIAM J. Discrete Math. 35 (2021) 948-952] completely confirmed this conjecture. From Brouwer and Gu's result τ(G)≥\fracdλ-1, we know that if G is a connected d-regular graph and λ≤(bd)/(b+1), then τ(G)≥(1)/(b) for an integer b≥1. Inspired by the above result and utilizing typical spectral techniques and graph construction methods from Cioabă et al. [J. Combin. Theory Ser. B 99 (2009) 287-297], we prove that if G is a connected d-regular graph and λ2(G)<ϕ(d,b), then τ(G)≥(1)/(b). Meanwhile, we construct graphs implying that the upper bound on λ2(G) is best possible. Our theorem strengthens the result of Chen et al. [Discrete Math. 348 (2025) 114404]. Finally, we also prove an upper bound of λb+1(G) to guarantee a connected d-regular graph to be (1)/(b)-tough.