Lower bounds for the algebraic connectivity of graphs with specified subgraphs

Zoran Stanic


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)>π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 ≤ pa(Gi)≥a(Pni), with ni ≥ 2, and, for p + 1 ≤ i ≤ qa(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
a(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.


edge-disjoint subgraphs, Laplacian matrix, algebraic connectivity, geometric mean, Hamiltonian cycle

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.2


N.M.M. de Abreu, Old and new results on algebraic connectivity of graphs, Linear Algebra Appl., 423 (2007), 53–73.

B. Bollobas and V. Nikiforov, Graphs and Hermitian matrices: eigenvalue interlacing. Discrete Math. 289 (2004), 119–127.

D. Christofides, D. Kuhn, and D. Osthus, Edge-disjoint Hamilton cycles in graphs, J. Combin. Theory B, 102 (2012), 1035–1060.

K. Ch. Das, Proof of conjectures involving algebraic connectivity of graphs, Linear Algebra Appl., 438 (2013), 3291–3302.

M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J., 23 (1973), 298–305.

M. Haythorpe, Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles, Electron. J. Graph Theory Appl., 4 (1) (2016), 18–25.

B. Jackson, Edge-disjoint Hamilton cycles in regular graphs of large degree, J. London Math. Soc., 19 (1979), 13–16.

B. Mohar, Eigenvalues, diameter, and mean distance in graphs, Graph Combinator., 7 (1991), 53–64.

C. St. J. A. Nash-Williams, Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency, in: L. Mirsky (Ed.), Studies in Pure Mathematics, Academic Press, 1971, pp. 157– 183.

A. A. Rad, M. Jalili, and M. Hasler, A lower bound for algebraic connectivity based on the connection-graph-stability method, Linear Algebra Appl., 435 (2011), 186–192.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats