Efficient and Perfect domination on circular-arc graphs
Min Chih Lin, Michel J. Mizrahi, Jayme Luiz SZWARCFITER · Electronic Notes in Discrete Mathematics · 2015
Given a graph G = ( V , E ) , a perfect dominating set is a subset of vertices V ′ ⊆ V ( G ) such that each vertex v ∈ V ( G ) \ V ′ is dominated by exactly one vertex v ′ ∈ V ′ . An efficient dominating set is a perfect dominating set V ′ where V ′ is also an independent set. These problems are usually posed in terms of edges instead of vertices. Both problems, either for the vertex or edge variant, remains NP-Hard, even when restricted to certain graphs families. We study both variants of the problems for the circular-arc graphs, and show efficient algorithms for all of them.