Efficient domination for classes of P₆-free graphs

Abstract: Let

G

be a finite undirected graph. A vertex {em dominates} itself and all its neighbors in

G

. A vertex set

D

is an {em efficient dominating set} (emph{e.d.} for short) of

G

if every vertex of

G

is dominated by exactly one vertex of

D

. The emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d. in

G

, is known to be NP-complete even for very restricted graph classes such as

P_{7}

-free chordal graphs. The ED problem on a graph

G

can be reduced to the Maximum Weight Independent Set (MWIS) problem on the square of

G

. The complexity of the ED problem is an open question for

P_{6}

-free graphs and was open even for the subclass of

P_{6}

-free chordal graphs. In this paper, we show that squares of

P_{6}

-free chordal graphs that have an e.d. are chordal; this even holds for the larger class of (

P_{6}

, house, hole, domino)-free graphs. This implies that ED/WeightedED is solvable in polynomial time for (

P_{6}

, house, hole, domino)-free graphs; in particular, for

P_{6}

-free chordal graphs. Moreover, based on our result that squares of

P_{6}

-free graphs that have an e.d. are hole-free and some properties concerning odd antiholes, we show that squares of (

P_{6}

, house)-free graphs ((

P_{6}

, bull)-free graphs, respectively) that have an e.d. are perfect. This implies that ED/WeightedED is solvable in polynomial time for (

P_{6}

, house)-free graphs and for (

P_{6}

, bull)-free graphs (the time bound for (

P_{6}

, house, hole, domino)-free graphs is better than that for (

P_{6}

, house)-free graphs). The complexity of the ED problem for

P_{6}

-free graphs remains an open question.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: Efficient domination for classes of \(P_6\)-free graphs