Algebraic connectivity of the second power of a graph

Abstract

Denote the Laplacian of a graph $G$ by $L(G)$ and its second smallest Laplacian eigenvalue by ${\lambda }_2(G)$. If $G$ is a graph on $n\ge 2$ vertices, then it is shown that the second smallest eigenvalue of $L(G)+\frac{1}{n}L(\overline{G^2})$ is at least 1, where $\overline{G^2}$ is the complement of the second power of $G$. As a corollary of this result, it is shown that \begin{itemize} \item $n{\lambda }_2(G)\ge {\lambda }_2(G^2),$ \item ${\lambda }_2(G)\ge 1-\frac{|D_G|}{n},$ \item $ λ_2(G) + λ_2(\Gb) \ge 1, $ \end{itemize} where $|D_G|$ is the number of vertices of eccentricity at least 3 in $G$.

arXiv comment8 pages, correct some typos, rewrite abstract, same as the version published in the JGT

References in corpus (1)

• The Algebraic Connectivity of a Graph and its Complement