Triangular Line Graphs

Problem and Results Summary

For a graph $G$, the **triangular line graph** $T(G)$ is the graph with vertex set given by the edges of $G$, and two edges of $G$ are adjacent in $T(G)$ if and only if they are incident in $G$ and span a triangle.
While recognizing line graphs is polynomial-time solvable, recognizing triangular line graphs is NP-complete.
An important feature that allows this is that there are possibly several *preimages*: multiple non-isomorphic graphs $H$ such that $T(H) \cong G$.
Specifically, the *7-sun* has exactly two preimages and can be used to encode the variables of a 3-CNF formula.

Research Papers

P. Anand, H. Escuadro, R. Gera, S. G. Hartke, D. Stolee,
On the hardness of recognizing triangular line graphs,
*Discrete Mathematics*,
**312**, 2627-2638.

Web Version ArXiv Version Official Version

Web Version ArXiv Version Official Version