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 (Formula presented) holds for every non-trivial graph G which contains edge-disjoint spanning subgraphs G1, G2, …, Gq such that, for 1 i p, a (Gi) a (Pni), with ni 2, and, for p+ 1 i q, a (Gi) a (Cni), where Pni and Cni 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 (Formula presented) ≥ − 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.