Perfect graphs for domination games

Csilla Bujt\'as; Sandi Klav\v{z}ar; Vesna Ir\v{s}i\v{c}

REVIEW 3 major objections 3 minor 24 references

Perfect graphs for domination games

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Domination-game perfect graphs reduce to a recursive two-operation construction.

desk verdict A solid structural characterization of γ_g-perfect graphs, with one load-bearing finite check that needs to be written out. read the letter →

arxiv 1908.09513 v1 pith:TTOJ6ZVG submitted 2019-08-26 math.CO

Csilla Bujtás , Vesna Iršič , Sandi Klavžar This is my paper · ORCID

classification math.CO MSC 05C5705C6968Q25

keywords dominationgamenumberperfectgraphsforgameshereditarygraphpropertiesrecursivecharacterizationrecognitionalgorithmcographstotal

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks when the game domination number $\gamma_g(F)$ of a graph agrees with the ordinary domination number $\gamma(F)$ not just for the graph itself but for every induced subgraph. It proves that this hereditary equality holds exactly for graphs that can be built from a single vertex by repeatedly adding a disjoint complete graph or adding a vertex joined to everything outside a chosen perfect set of cliques. The result matters because it turns an apparently global condition into a small recursive local one, yields a polynomial-time recognition algorithm, and implies that every minimal counterexample (a minimally $\gamma_g$-imperfect graph) has domination number 2. For the total version of the game the paper obtains an even simpler description: $\gamma_{tg}$-perfect graphs are exactly the $2P_3$-free cographs.

What carries the argument

The key objects are a graph invariant and a construction. A perfect set of cliques (PSC) in $F$ is a family of homogeneous cliques (cliques whose vertices all have identical closed neighborhoods) such that any two distinct cliques are at distance 3 and the open neighborhoods outside the cliques are completely joined. The operator $O(F,v,Q)$ adds a new vertex $v$ adjacent to every vertex of $F$ outside the union of the cliques in $Q$. The argument works by showing that a graph is $2$-$\gamma_g$-perfect exactly when, for a maximum-degree vertex in the contraction that collapses true twins, the leftover vertices form a PSC, which reduces the graph to a smaller one of the same kind; Proposition 3.6, a six-vertex case check, is what forces this decomposition and rules out the alternative configurations.

What would settle it

Run the check behind Proposition 3.6: take any graph containing vertices $u,v$ with two independent vertices in $N[u]\setminus N[v]$ and two independent vertices in $N[v]\setminus N[u]$, and inspect the induced six-vertex bipartite graph $H$ on those six vertices. If $H$ is neither isomorphic to one of the six graphs in $\mathcal{F}$ nor contains $P_5$ as an induced subgraph, the proposition is false and the main theorem collapses. Equivalently, a computer search over all graphs up to ten vertices looking for a $2$-$\gamma_g$-perfect graph with such a pair would also settle the claim.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 3.7: for every graph $G$, the following three statements are equivalent: $G$ is $\gamma_g$-perfect; $G$ is $2$-$\gamma_g$-perfect (the equality $\gamma_g(F)=\gamma(F)$ holds for every induced subgraph $F$ with $\gamma(F)=2$); and $G$ is obtainable from $K_1$ by finitely many applications of the disjoint-union-with-$K_s$ operation and the operator $O(F,v,Q)$, where $Q$ is a perfect set of cliques in $F$. The proof first decomposes every $2$-$\gamma_g$-perfect graph around a maximum-degree vertex of the true-twin contracted graph, showing that the vertices outside its closed neighborhood form a perfect set of cliques; it then shows that the two building operations preserve the relevant game-domination equality. A direct consequence is that every minimally $\gamma_g$-imperfect graph has domination number 2, and the recursively defined structure gives a polynomial recognition algorithm.

Load-bearing premise

The classification stands on a six-vertex case check in Proposition 3.6: whenever two vertices each have two non-adjacent neighbors that the other vertex lacks, the six-vertex subgraph they induce must be one of the listed forbidden graphs or contain $P_5$; if that finite verification is incomplete, the recursive characterization and the polynomial recognition algorithm lose their foundation.

Editorial extensions

If this is right

$\gamma_g$-perfect graphs can be recognized in polynomial time by repeatedly deleting a maximum-degree vertex (after contracting true twins) and checking that the outside vertices form a perfect set of cliques.
Every minimally $\gamma_g$-imperfect graph has domination number 2, so the search for forbidden induced subgraphs for $\gamma_g$-perfectness reduces to checking subgraphs with a two-vertex dominating set.
The only minimally $\gamma_g$-imperfect triangle-free graphs are $P_5$, $C_5$, and the six graphs of the family $\mathcal{F}$; in particular the only minimally $\gamma_g$-imperfect trees are $P_5$ and $F_2$.
$\gamma_{tg}$-perfect graphs are precisely the $2P_3$-free cographs, and $\gamma'_{tg}$-perfect graphs are precisely cographs; $\gamma'_g$-perfect graphs are precisely disjoint unions of cliques.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extension: This suggests that the hereditary equality of game and ordinary domination is controlled entirely by subgraphs of domination number at most 2, so one could test game-domination perfectness on larger graphs by focusing only on those local obstructions.
Extension: The recursive decomposition around a maximum-degree vertex may transfer to other domination-type games that admit a similar second-neighborhood lemma, giving a template for polynomial recognition of other hereditary game invariants.
Extension: The paper's enumeration up to nine vertices and its triangle-free classification support the stated conjecture that the listed graphs are the only minimally $\gamma_g$-imperfect graphs; an automated search aimed at the remaining cases would either confirm it or produce a new minimal example.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Worth a serious look. The paper defines γ_g-perfect graphs (hereditary equality between game domination and ordinary domination), proves they are exactly the graphs built from K1 by adding disjoint complete graphs and the operator O(G,v,Q) for a perfect set of cliques Q. That recursive characterization is genuinely new and gives a poly-time recognition algorithm as a byproduct. The proof strategy is sound: show 2-γ_g-perfect ≡ γ_g-perfect, then prove both directions of the construction theorem using a structural lemma about degree-maximal vertices. The minimally γ_g-imperfect result (domination number 2) is a clean consequence.

The main soft spot is Proposition 3.6. It asserts a six-vertex classification of induced subgraphs arising from two vertices with mutually non-dominated independent pairs, and the proof is just 'Checking all the possibilities...' with no enumeration. This claim is load-bearing: Theorem 3.9 uses it in Claims 1, 2, 4 to rule out alternatives, and Theorem 3.9 is the engine for both directions of Theorem 3.7. The stress-test note is right to flag it. It is a small finite check (32 edge patterns up to symmetry, if I count right), and the surrounding argument is internally consistent, so the gap is probably not a real error. But for a characterization theorem, the enumeration should be displayed in a table or appendix. A referee should ask for that.

Also note the abstract says 'overline{2P3}-free cographs' while the body and Proposition 5.2 say (P4,2P3)-free (i.e., 2P3-free cographs). That's a typo, not a mathematical issue.

The computer search in the concluding remarks verifies the conjectured list of minimally imperfect graphs up to 9 vertices. That's nice supporting evidence, but it doesn't replace the missing case check.

Overall: the central claim holds up, the presentation is clear, the citation pattern is fine (the one self-citation to [18] is to a published result used as a lemma, not a circular move). For anyone working on domination games, this is a useful paper. I'd send it to review with a request to make Proposition 3.6 fully explicit.

Referee Report

3 major / 3 minor

Summary. The paper studies hereditary equalities between game domination numbers and ordinary domination numbers. It defines γ_g-perfect graphs as graphs all of whose induced subgraphs satisfy γ_g(F)=γ(F), and proves (Theorems 3.7 and 3.8) that γ_g-perfect graphs are exactly the graphs constructible from K1 by disjoint union with complete graphs and an operator O(F,v,Q) based on perfect sets of cliques, and that every minimally γ_g-imperfect graph has domination number 2. It also gives a polynomial recognition algorithm, classifies triangle-free γ_g-perfect and minimally γ_g-imperfect graphs, and characterizes the total-game analogues. The proof strategy introduces 2-γ_g-perfect graphs and uses structural lemmas about homogeneous cliques and a finite case analysis.

Significance. If correct, the recursive characterization and polynomial recognition algorithm would be a substantial contribution to the theory of the domination game. The paper also provides a useful conceptual framework with homogeneous cliques and the operator O, and it reports computer-verified data up to 9 vertices. However, the central claim is false: elementary graphs such as P5 and C5 contradict the asserted list of minimally γ_g-imperfect graphs. The paper's core theorems therefore do not hold as stated.

major comments (3)

[§3.2, Proposition 3.5(i)] The claim that P5 is minimally γ_g-imperfect is false. In the D-game on P5 with vertices 1-2-3-4-5, Dominator can open at vertex 2. This dominates {1,2,3}, leaving {4,5} undominated. Whichever of 4 or 5 Staller next selects, its closed neighborhood covers the remaining vertices, so the game ends in two moves. Hence γ_g(P5) ≤ 2, and since γ(P5)=2, γ_g(P5)=2. Every proper induced subgraph of P5 is a disjoint union of paths of length at most 4, and each is directly checked to satisfy γ_g=γ. Thus P5 is actually γ_g-perfect, not minimally γ_g-imperfect.
[§3.2, Proposition 3.5(iii) and §3.3, Theorem 3.7] The same error afflicts the anti-hole claim. The anti-hole C5 is isomorphic to C5, and in C5 Dominator's first move at any vertex leaves exactly two adjacent undominated vertices; Staller's forced reply dominates the whole graph, so γ_g(C5)=γ(C5)=2. Thus C5 is not minimally γ_g-imperfect. More importantly, Proposition 3.4(ii) is false: P5 and C5 satisfy γ=γ_g=2, yet neither has a vertex v such that V(G)\N[v] induces a homogeneous clique. Since Proposition 3.4(ii) is used to support Proposition 3.5, and since P5 is used throughout the proofs of Theorem 3.9 and Theorem 3.11 as the canonical induced subgraph forcing imperfection, the equivalence in Theorem 3.7 collapses. In fact P5 is a direct counterexample to the recursive characterization, because it is γ_g-perfect but is not constructible by the two operators.
[§3.2, Proposition 3.6] Even apart from the false game values, Proposition 3.6 is not proved. The proof consists only of the sentence 'Checking all the possibilities, we get that H is either isomorphic to a minimally γ_g-imperfect graph from F, or contains P5.' This proposition is invoked in Claims 1, 2, and 4 of Theorem 3.9 and is load-bearing for the structure theory. The finite enumeration of the six-vertex bipartite graphs must be exhibited before the argument can be accepted.

minor comments (3)

[§4.2, Theorem 4.6] The case analysis in the proof of Theorem 4.6 repeatedly says 'contains an induced F_i' without displaying the induced subgraphs, and one subcase is dismissed with 'all cases can be easily checked'. These checks should be made explicit or tabulated.
[§3.2, Proposition 3.5(iv)] Proposition 3.5(iv) asserts that each graph in F is minimally γ_g-imperfect and says only that they 'can be checked one-by-one'. A table verifying γ_g(F)=3 and γ(F)=2 for each F_i would be more appropriate for a formal proof.
[§6, Table 1] The computer search results in Table 1 must be consistent with the correct game values; since C5 is listed among the two minimally γ_g-imperfect graphs on 5 vertices, the underlying computation appears to implement the game incorrectly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the recursive characterization is proved from game rules and independent structural lemmas, not assumed.

full rationale

The paper's central claim, Theorem 3.7, is not circular. The classes "γg-perfect" and "2-γg-perfect" are defined from the game domination number, while the recursive construction via disjoint union with complete graphs and the operator O(G,v,Q) is an independent combinatorial object. The proof derives the equivalence in both directions: Theorem 3.11 shows that every 2-γg-perfect graph has the recursive form, and Theorem 3.9 plus Proposition 3.12 show that the operators preserve the relevant game-domination equality. None of the definitions of the target property is smuggled into the operator construction. The only self-citation, Proposition 3.4 from reference [18], concerns small game domination numbers and is external, parameter-free support; it does not assume perfectness or the recursive characterization, so it does not create circularity. The main caveat is Proposition 3.6, whose proof says "Checking all the possibilities" without displaying the six-vertex enumeration; this is a potential completeness gap in the proof, not a circularity, because the case check is a finite independent verification. The derivation chain is otherwise self-contained and the characterization does not reduce to its own inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central characterization rests on standard game definitions, the external small-case characterization of γ_g-graphs, and several finite case checks. There are no fitted parameters and no invented physical entities; the only new notions are combinatorial objects defined in the paper.

assumptions (4)

standard math Optimal play in the domination game and total domination game is well defined, and each game domination number is always at least the corresponding static domination number.
This inequality is the basis for defining perfectness; it is used throughout Section 1 and the proof of Theorem 3.7.
domain assumption Proposition 3.4, taken from Ref. [18], characterizes graphs with game domination number equal to 1 or 2.
This external result is used to certify the minimally γ_g-imperfect graphs in Proposition 3.5, in Lemma 3.10, and in Theorem 3.9 when identifying optimal start vertices.
standard math Cographs are exactly P4-free graphs, equivalently graphs constructible from K1 by disjoint union and join (Ref. [9]).
Used in Propositions 5.2 and 5.3 for the total game perfectness characterizations.
ad hoc to paper The finite case checks in Proposition 3.5(iv), Proposition 3.6, and Theorem 4.6 correctly identify the claimed minimally γ_g-imperfect graphs.
These checks are summarized rather than itemized in the text; they are load-bearing for the minimal imperfect graph classification but not fully derived.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Perfect graphs for domination games." pith.science (2026). https://pith.science/paper/TTOJ6ZVG

@misc{pith2026190809513,
  author       = {Pith},
  title        = {Pith review of: Perfect graphs for domination games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TTOJ6ZVG}},
  note         = {Machine review of arXiv:1908.09513}
}

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.

Figures

Figures reproduced from arXiv: 1908.09513 by the authors.

**Figure 1.** An illustration of the operator O(G, v,Q). The thick lines represent joins between the connected sets, N′ i = N′ G (Qi), and N′ j = N′ G (Qj). When referring to the operators, we will always assume that s ∈ N and Q is a PSC in G. Note that, under this assumption, γ(G) ≥ ∣Q∣ must be true as dG(Qi , Qj) > 2 for every homogeneous cliques Qi and Qj from Q and therefore, the domination of the entire V (Q) needs at least … view at source ↗

**Figure 2.** The six graphs contained in F. From left to right, we denote them by F1, . . . , F6. Second, recall that the co-domino graph is the graph shown in [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Co-domino (left) and the complement of C6 (right). Proposition 3.5 The following graphs are minimally γg-imperfect: (i) the path P5; (ii) the co-domino; (iii) the anti-hole Cn for every n ≥ 5; (iv) each graph from F. Proof. The graphs referred to in (i), (ii), and (iv) can be checked one-by-one by using Proposition 3.4. For an anti-hole Cn with n ≥ 5, we first observe that γ(Cn) = 2 as any two independent vertices f… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: A construction of a γg-perfect graph. At the steps where operator O is applied, the PSC is marked in black and the newly added vertex is slightly larger. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

[18]

Klavˇ zar, G

S. Klavˇ zar, G. Koˇ smrlj, S. Schmidt, On graphs with small game domination number, Appl. Anal. Discrete Math. 10 (2016) 30–45

work page 2016
[1]

J. D. Alvarado, S. Dantas, D. Rautenbach, Perfectly relating t he domination, total domination, and paired domination numbers of a graph, Discre te Math. 338 (2015) 1424–1431

work page 2015
[2]

Arumugam, Bibin K

S. Arumugam, Bibin K. Jose, Cs. Bujt´ as, Zs. Tuza, Equality of d omination and transversal numbers in hypergraphs, Discrete Appl. Math. 161 ( 2013) 1859– 1867

work page 2013
[3]

On the equality of domination number and $ 2 $-domination number

G. Boruzanlı Ekinci, Cs. Bujt´ as, On the equality of domination nu mber and 2-domination number, arXiv:1907.07866

work page Pith review arXiv 1907
[4]

Breˇ sar, S

B. Breˇ sar, S. Klavˇ zar, D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991

2010
[5]

Bujt´ as, On the game total domination number, Graphs Com bin

Cs. Bujt´ as, On the game total domination number, Graphs Com bin. 34 (2018) 415–425

work page 2018
[6]

Bujt´ as, M.A

Cs. Bujt´ as, M.A. Henning, Zs. Tuza, Transversal game on hyp ergraphs and the 3 4-conjecture on the total domination game, SIAM J. Discrete Math . 30 (2016) 1830–1847

work page 2016
[7]

Camby, F

E. Camby, F. Plein, A note on an induced subgraph characterizat ion of domi- nation perfect graphs, Discrete Appl. Math. 217 (2017) 711–717 . 21

work page 2017

Show all 24 references

[8]

Chudnovsky, N

M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The st rong perfect graph theorem, Ann. of Math. 164 (2006) 51–229

2006
[9]

D. G. Corneil, H. Lerchs, L. Stewart Burlingham, Complement red ucible graphs, Discrete Appl. Math. 3 (1981) 163–174

1981
[10]

Dorbec, G

P. Dorbec, G. Koˇ smrlj, G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015) 71–79

2015
[11]

Henning, S

M.A. Henning, S. J¨ ager, D. Rautenbach, Hereditary equality of domination and exponential domination, Discuss. Math. Graph Theory 38 (2018) 2 75–285

2018
[12]

Henning, S

M.A. Henning, S. Klavˇ zar, D.F. Rall, Total version of the dominat ion game, Graphs Combin. 31 (2015) 1453–1462

2015
[13]

Henning, S

M.A. Henning, S. Klavˇ zar, D.F. Rall, The 4 /slash.left 5 upper bound on the game total domination number, Combinatorica 37 (2017) 223–251

2017
[14]

M. A. Henning, S. Klavˇ zar, D. F. Rall, Game total domination crit ical graphs, Discrete Appl. Math. 250 (2018) 28–37

2018
[15]

M. A. Henning, A. Yeo, Total Domination in Graphs, Springer, Ne w York, 2013

2013
[16]

James, S

T. James, S. Klavˇ zar, A. Vijayakumar, The domination game on split graphs, Bull. Aust. Math. Soc. 99 (2019) 327–337

2019
[17]

Kinnersley, D.B

W.B. Kinnersley, D.B. West, R. Zamani, Extremal problems for ga me domina- tion number, SIAM J. Discrete Math. 27 (2013) 2090–2107

2013
[19]

Klavˇ zar, D.F

S. Klavˇ zar, D.F. Rall, Domination game and minimal edge cuts, Disc rete Math. 342 (2019) 951–958

2019
[20]

Lov´ asz, Normal hypergraphs and the perfect graph con jecture, Discrete Math

L. Lov´ asz, Normal hypergraphs and the perfect graph con jecture, Discrete Math. 2 (1972) 253–267

1972
[21]

Nadjaﬁ-Arani, M

A.J. Nadjaﬁ-Arani, M. Siggers, H. Soltani, Charactertisation o f forests with trivial game domination numbers, J. Comb. Optim. 32 (2016) 800–81 1

2016
[22]

D. P. Sumner, J. I. Moore, Domination perfect graphs, Notice s Amer. Math. Soc. 26 (1979) A-569. 22

1979
[23]

K. Xu, X. Li, On domination game stable graphs and domination gam e edge- critical graphs, Discrete Appl. Math. 250 (2018) 47–56

2018
[24]

I. E. Zverovich, V. E. Zverovich, An induced subgraph charac terization of dom- ination perfect graphs, J. Graph Theory 20 (1995) 375–395. 23

1995

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [18]

Klavˇ zar, G

S. Klavˇ zar, G. Koˇ smrlj, S. Schmidt, On graphs with small game domination number, Appl. Anal. Discrete Math. 10 (2016) 30–45

work page 2016

[2] [1]

J. D. Alvarado, S. Dantas, D. Rautenbach, Perfectly relating t he domination, total domination, and paired domination numbers of a graph, Discre te Math. 338 (2015) 1424–1431

work page 2015

[3] [2]

Arumugam, Bibin K

S. Arumugam, Bibin K. Jose, Cs. Bujt´ as, Zs. Tuza, Equality of d omination and transversal numbers in hypergraphs, Discrete Appl. Math. 161 ( 2013) 1859– 1867

work page 2013

[4] [3]

On the equality of domination number and $ 2 $-domination number

G. Boruzanlı Ekinci, Cs. Bujt´ as, On the equality of domination nu mber and 2-domination number, arXiv:1907.07866

work page Pith review arXiv 1907

[5] [4]

Breˇ sar, S

B. Breˇ sar, S. Klavˇ zar, D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991

2010

[6] [5]

Bujt´ as, On the game total domination number, Graphs Com bin

Cs. Bujt´ as, On the game total domination number, Graphs Com bin. 34 (2018) 415–425

work page 2018

[7] [6]

Bujt´ as, M.A

Cs. Bujt´ as, M.A. Henning, Zs. Tuza, Transversal game on hyp ergraphs and the 3 4-conjecture on the total domination game, SIAM J. Discrete Math . 30 (2016) 1830–1847

work page 2016

[8] [7]

Camby, F

E. Camby, F. Plein, A note on an induced subgraph characterizat ion of domi- nation perfect graphs, Discrete Appl. Math. 217 (2017) 711–717 . 21

work page 2017