On the hardness of recognizing triangular line graphs

View/ Open
Author
Anand, Pranav
Escuadro, Henry
Gera, Ralucca
Hartke, Stephen G.
Stolee, Derrick
Date
2010Metadata
Show full item recordAbstract
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.
Description
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
Collections
Related items
Showing items related by title, author, creator and subject.
-
Number of test samples needed to obtain a desired Bayesian confidence interval for a proportion.
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 ... -
A characterization of graphs with interval two-step graphs
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 ... -
A Characterization of Graphs With Interval Two-Step Graphs
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 ...