An Equation Involving the Neighborhood (Two-Step) and Line Graphs

Mary M.Miller1, Robert C.Brigham1, Ronald D.Dutton2
1Department of Mathematics
2 Department of Computer Science University of Central Florida Orlando, FL 32816

Abstract

The neighborhood or two-step graph, \(N(G)\), of a graph \(G\) is the intersection graph of the open neighborhoods of the vertices of \(G\), and \(L(G)\) is the line graph of \(G\). The class of graphs for which \(N[L(G)] \equiv L[N(G)]\) consists of those graphs for which every component is either \(K_1\), \(K_{1,3}\), or \(C_n\) where \(n \geq 3\) and \(n \neq 4\).