论文标题
图的图表至少2个位于三角形的图表
Graphs whose vertices of degree at least 2 lie in a triangle
论文作者
论文摘要
吊坠顶点是第一度，一个孤立的顶点的度为零。一个无邻恒星（简短的NSF）图是一个图形，其中每个顶点都包含在吊坠顶点和孤立顶点以外的三角形中。此类以前已经在几种情况下考虑过。在本文中，我们研究了NSF图的主导诱导匹配（DIM）问题和完美的边缘统治（PED）问题的复杂性。我们证明，相应的决策问题对于其几个子类是NP的完整问题。作为这项研究的附加值，我们显示了平面正1In3SAT的三个连接变体也是NP完整的。由于这些变体在复杂性理论上下文中比许多图形问题更为基础，因此这些结果对于证明其他问题是NP综合问题是有用的。
A pendant vertex is one of degree one and an isolated vertex has degree zero. A neighborhood star-free (NSF for short) graph is one in which every vertex is contained in a triangle except pendant vertices and isolated vertices. This class has been considered before for several contexts. In the present paper, we study the complexity of the dominating induced matching (DIM) problem and the perfect edge domination (PED) problem for NSF graphs. We prove the corresponding decision problems are NP-Complete for several of its subclasses. As an added value of this study, we have shown three connected variants of planar positive 1in3SAT are also NP-Complete. Since these variants are more basic in complexity theory context than many graph problems, these results can be useful to prove that other problems are NP-Complete.
