### 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*)>*π*^{2}/3(*p*(12**g**(*n*_{1}, *n*_{2}, …, *n*_{p})^{2} − *π*^{2})/4**g**(*n*_{1}, *n*_{2}, …, *n*_{p})^{4} + 4(*q* − *p*)(3**g**(*n*_{p + 1}, *n*_{p + 2}, …, *n*_{q})^{2} − *π*^{2})/**g**(*n*_{p + 1}, *n*_{p + 2}, …, *n*_{q})^{4}),

holds for every non-trivial graph *G* which contains edge-disjoint spanning subgraphs *G*_{1}, *G*_{2}, …, *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*)>*π*^{2}12(4*q* − 3*p*)*n*^{2} − (16*q* − 15*p*)*π*^{2}/12*n*^{4},

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

#### Full Text:

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

#### References

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.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

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