2014/09/05 by T. Karthick, Karthick, T.
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 #Optimization and Search Problems #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1409.1676
arxiv created 2014/09/05 · openalex publication_date 2014/09/05 · arxiv updated 2014/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a graph G, an \it 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 Efficient Dominating Set problem (EDS) asks for the existence of an efficient dominating set in a given graph G. The EDS is known to be NP-complete for P7-free graphs, and is known to be polynomial time solvable for P5-free graphs. However, the computational complexity of the EDS problem is unknown for P6-free graphs. In this paper, we show that the EDS problem can be solved in polynomial time for a subclass of P6-free graphs, namely (P6, banner)-free graphs.