Vertex-connectivity and eigenvalues of graphs with fixed girth

摘要

Let κ(G), g(G), δ(G) and Δ(G) denote the vertex-connectivity, the girth, the minimum degree and the maximum degree of a simple graph G, and let λi(G), μi(G) and qi(G) denote the ith largest adjacency eigenvalue, Lapalcian eigenvalue and signless Laplacian eigenvalue of G. We investigate functions f(δ, Δ, g, k) with Δ ≥ δ ≥ k ≥ 2 and g ≥ 3 such that any graph G satisfying λ2(G) < f(δ(G), Δ(G), g(G), k) has connectivity κ(G) ≥ k. Analogues results involving the Laplacian eigenvalues and the signless Laplacian eigenvalues to describe connectivity of a graph are also presented. As corollaries, we show that for an integer k ≥ 2 and a simple graph G with n=|V(G)|, maximum degree Δ and minimum degree δ ≥ k, the connectivity κ(G) ≥ k if one of the following holds.(i)λ2(G)<δ−(k−1)Δn2(δ−k+2)(n−δ+k−2), or(ii)μn−1(G)>(k−1)Δn2(δ−k+2)(n−δ+k−2), or(iii)q2(G)<2δ−(k−1)Δn2(δ−k+2)(n−δ+k−2).