2019/08/26 by Csilla Bujtás, Bujtás, Csilla, Vesna Iršič +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1908.09513
arxiv created 2019/08/26 · arxiv updated 2019/08/27
Let γg(G) and γtg(G) be the game domination number and the total game domination number of a graph G, respectively. Then G is γg-perfect (resp. γtg-perfect), if every induced subgraph F of G satisfies γg(F)=γ(F) (resp. γtg(F)=γt(F)). A recursive characterization of γg-perfect graphs is derived. The characterization yields a polynomial recognition algorithm for γg-perfect graphs. It is proved that every minimally γg-imperfect graph has domination number 2. All minimally γg-imperfect triangle-free graphs are determined. It is also proved that γtg-perfect graphs are precisely 2P3-free cographs.