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 thata(G)>π2/3(p(12g(n1, n2, …, np)2 − π2)/4g(n1, n2, …, np)4 + 4(q − p)(3g(np + 1, np + 2, …, nq)2 − π2)/g(np + 1, np + 2, …, nq)4),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 bounda(G)>π212(4q − 3p)n2 − (16q − 15p)π2/12n4,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.

Keywords

• edge-disjoint subgraphs, laplacian matrix, algebraic connectivity, geometric mean, hamiltonian cycle