Connectivity and eigenvalues of graphs with given girth or clique number

• Published in: Linear algebra and its applications 2020-12, Vol.607, p.319-340
• Main Authors: Hong, Zhen-Mu, Lai, Hong-Jian, Xia, Zheng-Jiang
• Format: Article
• Language: English
• Subjects: Algebraic connectivity; Apexes; Clique number; Connectivity; Edge-connectivity; Eigenvalue; Eigenvalues; Girth; Graph theory; Graphs; Linear algebra; Vertex-connectivity
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2020.08.015

Let κ′(G), μn−1(G) and μ1(G) denote the edge-connectivity, the algebraic connectivity and the Laplacian spectral radius of G, respectively. In this paper, we prove that for integers k≥2 and r≥2, and any simple graph G of order n with minimum degree δ≥k, girth g≥3 and clique number ω(G)≤r, the edge-connectivity κ′(G)≥k if μn−1(G)≥(k−1)nN(δ,g)(n−N(δ,g)) or if μn−1(G)≥(k−1)nφ(δ,r)(n−φ(δ,r)), where N(δ,g) is the Moore bound on the smallest possible number of vertices such that there exists a δ-regular simple graph with girth g, and φ(δ,r)=max⁡{δ+1,⌊rδr−1⌋}. Analogue results involving μn−1(G) and μ1(G)μn−1(G) to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in Liu et al. (2013) [22], Liu et al. (2019) [20], Hong et al. (2019) [15], Liu et al. (2019) [21] and Abiad et al. (2018) [1] are improved or extended.