On efficient domination for some classes of H-free chordal graphs

作     者：Brandstadt, Andreas Mosca, Raffaele 

作者机构：Univ Rostock Inst Inforrnat D-18051 Rostock Germany Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2020年第281卷

页      面：81-95页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：We gratefully thank the anonymous reviewers for their comments and corrections. The second author would like to witness that he just tries to pray a lot and is not able to do anything without that - ad laudem Domini 

主　　题：Weighted efficient domination H-free chordal graphs NP-completeness Net-free chordal graphs Extended-gem-free chordal graphs S-1,S-2,S-3-free chordal graphs Polynomial time algorithm Clique-width 

摘      要：A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be NP-complete even for very restricted graph classes such as for 2P(3)-free chordal graphs while it is solvable in polynomial time for P-6-free chordal graphs (and even for P-6-free graphs). A standard reduction from the NP-complete Exact Cover problem shows that ED is NP-complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP-complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP-complete for butterfly-free chordal graphs while it is solvable in linear time for 2P(2)-free graphs. We show that (weighted) ED can be solved in polynomial time for H-free chordal graphs when H is net, extended gem, or S-1,S-2,S-3. (c) 2019 Elsevier B.V. All rights reserved.