6
$\begingroup$

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?

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

1 Answer 1

Reset to default
6
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .