On the hardness of recognizing triangular line graphs

DOI10.1016/J.DISC.2011.11.037zbMATH Open1408.68066arXiv1007.1178OpenAlexW1991938654MaRDI QIDQ442382FDOQ442382

Authors: Pranav Anand, Henry Escuadro, Ralucca Gera, Stephen G. Hartke, Derrick Stolee 

Publication date: 10 August 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a graph G, its triangular line graph is the graph T(G) with vertex set consisting of the edges of G and adjacencies between edges that are incident in G as well as being within a common triangle. Graphs with a representation as the triangular line graph of some graph G are triangular line graphs, which have been studied under many names including anti-Gallai graphs, 2-in-3 graphs, and link graphs. While closely related to line graphs, triangular line graphs have been difficult to understand and characterize. Van Bang Le asked if recognizing triangular line graphs has an efficient algorithm or is computationally complex. We answer this question by proving that the complexity of recognizing triangular line graphs is NP-complete via a reduction from 3-SAT.

Full work available at URL: https://arxiv.org/abs/1007.1178

Recommendations

• Generalized line graphs: Cartesian products and complexity of recognition
• The recognition problem for line bigraphs
• Hardness and algorithms for variants of line graphs of directed graphs
• The recognition of triangle graphs
• The recognition of triangle graphs

zbMATH Keywords

NP-completenessH-line graphtriangular line graph

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Title not available (Why is that?)
• Title not available (Why is that?)
• Transitiv orientierbare Graphen
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Gallai graphs and anti-Gallai graphs
• Convergence of sequences of iterated triangular line graphs
• Convergent sequences of iterated \(H\)-line graphs
• Reconstructing a graph from its arc incidence graph
• Triangular line graphs and word sense disambiguation
• Gallai and anti-Gallai graphs of a graph
• Title not available (Why is that?)

Cited In (13)

• The Gallai and anti-Gallai graphs of strongly regular graphs
• A survey of the studies on Gallai and anti-Gallai graphs
• New results and open problems in line graphs
• On an edge partition and root graphs of some classes of line graphs
• The recognition problem for line bigraphs
• Edge clique partition in \((k,\ell)\)-graphs
• EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS
• Generalized line graphs: Cartesian products and complexity of recognition
• Forests and trees among Gallai graphs
• Gallai and anti-Gallai graph operators
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• Hardness and algorithms for variants of line graphs of directed graphs
• Triangular line graphs and word sense disambiguation

This page was built for publication: On the hardness of recognizing triangular line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442382)