# Has anyone seen this graph construction that is similar to the line graph?

Given a graph $G$, its line graph, denoted $L(G)$, is the graph whose vertices are the edges of $G$ and where two edges of $G$ are adjacent in $L(G)$ if they are incident to each other, i.e., they share some endpoint. I am interested in the graph, let's call it $L'(G)$, whose vertices are the edges of $G$, two being adjacent if they are incident but not part of a triangle in $G$, i.e., the two vertices not shared by the edges are not adjacent in $G$. Obviously, for a triangle free graph $L(G)$ and $L'(G)$ are the same, but in general $L'(G)$ is just some spanning subgraph of $L(G)$.

Does anyone know if this construction has come up in the literature before?

• Haven't seen it, but that doesn't say a whole lot. – Pat Devlin Dec 20 '16 at 15:17

## 1 Answer

This graph is known as $\Gamma(G)$ (the corresponding construction in which the edges span a triangle is called $\Delta(G)$) or also the Gallai graph of $G$.

See for example:

V.B. Le Gallai Graphs and Their Iteration Behavior Dissertation Thesis, TU Berlin 1994

V.B. Le Gallai graphs and anti-Gallai graphs Discrete Math. 159 1996 179--189

• Thanks! Any idea if anything is known about their spectral properties? – David Roberson Dec 20 '16 at 19:00
• Sorry, I don't know. – Ernst de Ridder Dec 21 '16 at 9:02