Derrick Stolee - Iowa State University - Research Browser

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

Derrick Stolee - Iowa State University - Research Browser