Perfect graphs for domination games

Abstract

Let ${\gamma }_g(G)$ and ${\gamma }_{tg}(G)$ be the game domination number and the total game domination number of a graph $G$, respectively. Then $G$ is ${\gamma }_g$-perfect (resp. ${\gamma }_{tg}$-perfect), if every induced subgraph $F$ of $G$ satisfies ${\gamma }_g(F)=\gamma (F)$ (resp. ${\gamma }_{tg}(F)={\gamma }_t(F)$). A recursive characterization of ${\gamma }_g$-perfect graphs is derived. The characterization yields a polynomial recognition algorithm for ${\gamma }_g$-perfect graphs. It is proved that every minimally ${\gamma }_g$-imperfect graph has domination number $2$. All minimally ${\gamma }_g$-imperfect triangle-free graphs are determined. It is also proved that ${\gamma }_{tg}$-perfect graphs are precisely $\overline{2P_3}$-free cographs.