On the hardness of recognizing triangular line graphs
Hartke, Stephen G.
MetadataShow full item record
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.
Discrete Math Volume 312, Issue 17 (2012)||The article of record as published may be located at http://dx.doi.org/10.1016/j.disc.2011.11.037
Showing items related by title, author, creator and subject.
Ipekkan, Ahmet Ziyaeddin (Monterey, California. Naval Postgraduate School, 1989);One recurring problem in military operational test and evaluation is determination of the number of items to test. This thesis describes a Bayesian method to determine the sample size that is needed to estimate a ...
Merz, Sarah K.; Rasmussen, Craig W.; Lundgren, J. Richard; Maybee, John Stanley (Monterey, California. Naval Postgraduate School, 1993); NPS-MA-93-021One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. In this paper we consider this problem for the class of loopless symmetric digraphs. Here we first ...
Lundgren, J. Richard; Merz, Sarah K.; Maybee, John S.; Rasmussen, Craig W. (Norrth-Holland, 1995);One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. This problem originated in the work of Cohen on food webs. We consider it for the class of loopless ...