کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648134 1342394 2012 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the hardness of recognizing triangular line graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the hardness of recognizing triangular line graphs
چکیده انگلیسی

Given a graph GG, its triangular line graph is the graph T(G)T(G) with vertex set consisting of the edges of GG and adjacencies between edges that are incident in GG as well as being within a common triangle. Graphs with a representation as the triangular line graph of some graph GG 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2627–2638
نویسندگان
, , , , ,