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?

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.