Algebraic Connectivity of the Line Graph, the Middle Graph and the Total Graph of a Regular Graph

Abstract

Let $G$ be a graph on $p$ vertices and denote by $L(G)=D(G)–A(G)$ the difference between the diagonal matrix of vertex degrees and the adjacency matrix. It is not difficult to see that $L(G)$ is positive semidefinite symmetric and its second smallest eigenvalue, $a(G)>0$, if and only if $G$ is connected. This observation led M. Fiedler to call $a(G)$ the algebraic connectivity of $G$.

The algebraic connectivity of the line graph, the middle graph, and the total graph of a regular graph are given.