On the Spectrum of Locally Linear Graphs

Abstract

For a locally linear graph $G$, which is a graph built out of triangles, it is possible to construct another graph $G^{\ast }$ that would consist of triangles of $G$ as vertices, while sharing (or not sharing) a common vertex between a pair of triangles would define a binary relation for edges of $G^{\ast }$. In this paper we show that the spectrum of $G^{\ast }$ is uniquely defined by $G$. We will also show some structural similarities of these graphs; in particular, that the number of quadrilaterals and pentagons in both graphs are the same; that $G^{\ast }$ does not contain $K_4-e$ and $K_{1,4}$; and that $G$ can be reconstructed from $G^{\ast }$.

arXiv comment7 pages, 2 figures