Finding Efficient Domination for S_1,1,5-Free Bipartite Graphs in Polynomial Time

2020/10/29 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1 · 2 citations
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.2010.16076

arXiv admin note: text overlap with arXiv:2008.04046

arxiv created 2021/03/17 · arxiv updated 2021/03/19

Abstract

A vertex set D in a finite undirected graph G is an \em 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 \NP-complete for various H-free bipartite graphs, e.g., Lu and Tang showed that ED is \NP-complete for chordal bipartite graphs and for planar bipartite graphs; actually, ED is \NP-complete even for planar bipartite graphs with vertex degree at most 3 and girth at least g for every fixed g. Thus, ED is \NP-complete for K_1,4-free bipartite graphs and for C₄-free bipartite graphs. In this paper, we show that ED can be solved in polynomial time for S_1,1,5-free bipartite graphs.

Citations

• Finding Efficient Domination for S_1,3,3-Free Bipartite Graphs in Polynomial Time

Cited by

• Finding Efficient Domination for P₈-Free Bipartite Graphs in Polynomial Time
• Finding Efficient Domination for (S_1,2,5,S_3,3,3-Free Chordal Bipartite Graphs in Polynomial Time

Related

• Finding Efficient Domination for S_1,3,3-Free Bipartite Graphs in Polynomial Time
• Finding Efficient Domination for (S_1,2,5,S_3,3,3-Free Chordal Bipartite Graphs in Polynomial Time
• Finding Efficient Domination for P₈-Free Bipartite Graphs in Polynomial Time
• On Efficient Domination for Some Classes of H-Free Bipartite Graphs
• On Efficient Domination for Some Classes of H-Free Chordal Graphs