Strong cliques and equistability of EPT graphs

详细信息    查看全文

• 作者：Liliana Alcó ; n^a ; ^{liliana@mate.unlp.edu.ar" class="auth_mail" title="E-mail the corresponding author} ; Marisa Gutierrez^a ; ^b ; ^{marisa@mate.unlp.edu.ar" class="auth_mail" title="E-mail the corresponding author} ; Istvá ; n Ková ; cs^c ; ^d ; ^{istvan.kovacs@upr.si" class="auth_mail" title="E-mail the corresponding author} ; Martin Milanič^c ; ^d ; ^{martin.milanic@upr.si" class="auth_mail" title="E-mail the corresponding author} ; Romeo Rizzi^e ; ^{romeo.rizzi@univr.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Equistable graph ; EPT graph ; Triangle graph ; General partition graph ; Triangle condition ; Strong clique
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 April 2016
• 年：2016
• 卷：203
• 期：Complete
• 页码：13-25
• 全文大小：513 K

文摘

In this paper, we characterize the equistable graphs within the class of EPT graphs, the edge-intersection graphs of paths in a tree. This result generalizes a previously known characterization of equistable line graphs. Our approach is based on the combinatorial features of triangle graphs and general partition graphs. We also show that, in EPT graphs, testing whether a given clique is strong is co-NP-complete. We obtain this hardness result by first showing hardness of the problem of determining whether a given graph has a maximal matching disjoint from a given edge cut. As a positive result, we prove that the problem of testing whether a given clique is strong is polynomial in the class of local EPT graphs, which are defined as the edge intersection graphs of paths in a star and are known to coincide with the line graphs of multigraphs.