On the hardness of recognizing triangular line graphs

DOI10.1016/J.DISC.2011.11.037MaRDI QIDQ442382zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 851097 (Why is no real title available?)
• scientific article; zbMATH DE number 861439 (Why is no real title available?)
• scientific article; zbMATH DE number 3102314 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Convergence of sequences of iterated triangular line graphs
• Convergent sequences of iterated \(H\)-line graphs
• Gallai and anti-Gallai graphs of a graph
• Gallai graphs and anti-Gallai graphs
• Reconstructing a graph from its arc incidence graph
• Transitiv orientierbare Graphen
• Triangular line graphs and word sense disambiguation

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)