Perfect graphs for domination games

Abstract: Let

g a m m a_{g} (G)

and

g a m m a_{t g} (G)

be the game domination number and the total game domination number of a graph

G

, respectively. Then

G

is

g a m m a_{g}

-perfect (resp.

g a m m a_{t g}

-perfect), if every induced subgraph

F

of

G

satisfies

g a m m a_{g} (F) = g a m m a (F)

(resp.

g a m m a_{t g} (F) = g a m m a_{t} (F)

). A recursive characterization of

g a m m a_{g}

-perfect graphs is derived. The characterization yields a polynomial recognition algorithm for

g a m m a_{g}

-perfect graphs. It is proved that every minimally

g a m m a_{g}

-imperfect graph has domination number

2

. All minimally

g a m m a_{g}

-imperfect triangle-free graphs are determined. It is also proved that

g a m m a_{t g}

-perfect graphs are precisely

o v e r l i n e 2 P_{3}

-free cographs.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Perfect graphs for domination games