Weighted efficient domination in two subclasses of -free graphs

详细信息    查看全文

• 作者：Andreas Brandstä ; dt^a ; ^{andreas.brandstaedt@uni-rostock.de" class="auth_mail" title="E-mail the corresponding author} ; T. Karthick^b ; ^{tlkrkiitm@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph algorithms ; Domination in graphs ; Efficient domination ; Perfect code ; P6P6-free graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 March 2016
• 年：2016
• 卷：201
• 期：Complete
• 页码：38-46
• 全文大小：412 K

文摘

In a graph G$G$, an efficient dominating set   is a subset D$D$ of vertices such that D$D$ is an independent set and each vertex outside D$D$ has exactly one neighbor in D$D$. The Efficient Dominating Set (ED) problem asks for the existence of an efficient dominating set in a given graph. The ED problem is known to be solvable in polynomial time for P₅$P_5$-free graphs but NP$NP$-complete for P₇$P_7$-free graphs whereas for P₆$P_6$-free graphs, its complexity was an open problem. Recently, Lokshtanov et al. and independently, Mosca showed that ED is solvable in polynomial time for P₆$P_6$-free graphs.

In this paper, we show that the ED problem can be solved efficiently for two subclasses of P₆$P_6$-free graphs, namely for (P₆$P_6$, bull)-free graphs, and for (P₆,S_1,1,3$P_6,S_{1,1,3}$)-free graphs; the time bounds for the two subclasses are much better than in the general case of P₆$P_6$-free graphs.