On minimum algebraic connectivity of graphs whose complements are bicyclic

Abstract

The second smallest eigenvalue of the Laplacian matrix of a graph (network) is called its algebraic connectivity which is used to diagnose Alzheimer’s disease, distinguish the group differences, measure the robustness, construct multiplex model, synchronize the stability, analyze the diffusion processes and find the connectivity of the graphs (networks). A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. In this paper, firstly the unique graph with a minimum algebraic connectivity is characterized in the class of connected graphs whose complements are bicyclic with exactly three cycles. Then, we find the unique graph of minimum algebraic connectivity in the class of connected graphs Ωnc=Ω1,nc∪Ω2,nc,$\begin{array}{} {\it\Omega}^c_{n}={\it\Omega}^c_{1,n}\cup{\it\Omega}^c_{2,n}, \end{array}$ where Ω1,nc$\begin{array}{} {\it\Omega}^c_{1,n} \end{array}$ and Ω2,nc$\begin{array}{} {\it\Omega}^c_{2,n} \end{array}$ are classes of the connected graphs in which the complement of each graph of order n is a bicyclic graph with exactly two and three cycles, respectively.

Keywords

• laplacian matrix
• eigenvalues
• algebraic connectivity
• 15a18
• 05c50
• 05c40
• 05d05