Lower bounds for the algebraic connectivity of graphs with specified subgraphs

Abstract

The second smallest eigenvalue of the Laplacian matrix of a graph G is called the algebraic connectivity and denoted by a(G). We prove that

a(G)>π²/3(p(12g(n₁, n₂, …, n_p)² − π²)/4g(n₁, n₂, …, n_p)⁴ + 4(q − p)(3g(n_p + 1, n_p + 2, …, n_q)² − π²)/g(n_p + 1, n_p + 2, …, n_q)⁴),

holds for every non-trivial graph G which contains edge-disjoint spanning subgraphs G₁, G₂, …,  G_q such that, for 1 ≤ i ≤ p, a(G_i)≥a(P_ni), with n_i ≥ 2, and, for p + 1 ≤ i ≤ q, a(G_i)≥a(C_ni), where P_ni and C_ni denote the path and the cycle of the corresponding order, respectively, and g denotes the geometric mean of given arguments. Among certain consequences, we emphasize the following lower bound
a(G)>π²12(4q − 3p)n² − (16q − 15p)π²/12n⁴,
referring to G which has n (n ≥ 2) vertices and contains p Hamiltonian paths and q − p Hamiltonian cycles, such that all of them are edge-disjoint. We also discuss the quality of the obtained lower bounds.