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.