On the hardness of recognizing triangular line graphs

Details On the hardness of recognizing triangular line graphs On the hardness of recognizing triangular line graphs

2010-07-07

arxiv.org/abs/1007.1178v1

Mathematics

Combinatorics

18 pages, 8 figures, 4 tables

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the hardness of recognizing triangular line graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the hardness of recognizing triangular line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the hardness of recognizing triangular line graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345887