Weighted Efficient Domination in Classes of P₆-free Graphs

2015/03/20 by Andreas Brandstädt, Andreas Brandstadt, Brandstadt, Andreas +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1503.06025

arxiv created 2015/03/20 · openalex publication_date 2015/03/20 · arxiv updated 2015/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In a graph G, an efficient dominating set is a subset D of vertices such that D is an independent set and each vertex outside D has exactly one neighbor in D. The Minimum Weight Efficient Dominating Set (Min-WED) problem asks for an efficient dominating set of total minimum weight in a given vertex-weighted graph; the Maximum Weight Efficient Dominating Set (Max-WED) problem is defined similarly. The Min-WED/Max-WED is known to be NP-complete for P₇-free graphs, and is known to be polynomial time solvable for P₅-free graphs. However, the computational complexity of the Min-WED/Max-WED problem is unknown for P₆-free graphs. In this paper, we show that the Min-WED/Max-WED problem can be solved in polynomial time for two subclasses of P₆-free graphs, namely for (P₆,S_1,1,3)-free graphs, and for (P₆, bull)-free graphs.

Cited by

• Weighted Independent Sets in a Subclass of P₆-free Graphs

Related

• Weighted Efficient Domination for P₆-Free Graphs in Polynomial Time
• New Polynomial Cases of the Weighted Efficient Domination Problem
• New polynomial case for efficient domination in P₆-free graphs
• Independence and Efficient Domination on P₆-free Graphs
• Weighted Efficient Domination for (P₅+kP₂)-Free Graphs in Polynomial Time