{"id":"e2f8e2ad-5a5a-4cdf-bfc3-c116efeea4b4","arxiv_id":"1908.09513","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A graph is γ_g-perfect exactly when it can be built from one vertex by adding complete graph components and by adding a vertex adjacent to everything except a perfect set of cliques; such graphs are recognizable in polynomial time.","lead":"This paper characterizes graphs where the game domination number matches the usual domination number in every induced subgraph. It gives a recursive construction and a polynomial-time recognition algorithm for those graphs, plus classifications for nearby game variants.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3.6's six-vertex case check is asserted but not shown; Theorem 3.9 and hence Theorem 3.7 depend on it, so the proof is incomplete pending explicit verification.","rationale":"The central claim is Theorem 3.7. Tracing dependencies, the only unshown step is Proposition 3.6. Proposition 3.6 is used essentially in Theorem 3.9: Claim 1 uses it to linearly order neighborhoods in N''; Claim 2 uses it to bound the number of non-complete sets N'_i; Claim 4 uses it in the final excluded case. Without Proposition 3.6, Theorem 3.9 fails, and the proof of (iii) implies (ii) and (ii) implies (i) in Theorem 3.7 has no replacement. I checked the surrounding steps in good faith: the induced-P5 arguments in Theorem 3.11 are valid, Lemma 3.10 follows from Proposition 3.4, and Proposition 3.12 is sound. The finite check in Proposition 3.6 is plausibly correct: the only bipartite graphs on these six vertices with the mandatory adjacencies and no induced P5 appear to be 2P3 and the double-star, both in F. But because the paper does not provide the enumeration, the proof is not complete at its most load-bearing point. This is a rigorousness concern, not a demonstrated counterexample. The right disposition is conditional acceptance pending the explicit verification of this six-vertex case analysis.","tokens_in":16117,"tokens_out":43891,"duration_ms":440035,"concrete_test":"Enumerate all 32 graphs on {u,v,x1,x2,y1,y2} with mandatory edges ux1, ux2, vy1, vy2, with {v,x1,x2} and {u,y1,y2} independent, and with optional edges uv, x1y1, x1y2, x2y1, x2y2. For each graph, test whether it contains an induced P5 or is isomorphic to one of F1,...,F6. This can be done by a short script or by hand using the six figures of F. If every P5-free case is isomorphic to a member of F, Proposition 3.6 holds and Theorem 3.7 stands; if a P5-free graph outside F occurs, the proof of Theorem 3.9 collapses.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The weakest load-bearing point is Proposition 3.6. It claims that whenever two vertices u and v have both NG[u]\\NG[v] and NG[v]\\NG[u] containing a nonadjacent pair, the induced six-vertex bipartite graph H is either isomorphic to a graph from F or contains an induced P5. The proof says only 'Checking all the possibilities...' and does not display the enumeration. This is not a stylistic gap: Theorem 3.9 invokes Proposition 3.6 in Claims 1, 2, and 4 to eliminate structural alternatives. Theorem 3.9 is then the engine for both directions of Theorem 3.7: it proves that O(G,v,Q) is a gamma_g-graph when G is 2-gamma_g-perfect, and it is used (with Theorem 3.11) to prove that every 2-gamma_g-perfect graph is recursively constructible. If the six-vertex classification is incomplete, the characterization and the polynomial recognition algorithm lose their support. I found no independent flaw in the surrounding argument: the P5 arguments, Lemma 3.10, and the case splits in Theorem 3.11 are internally consistent. The missing enumeration is small (32 edge patterns up to symmetry) and probably correct, but it must be exhibited or verified before the central claim is fully proven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16393,"tokens_out":33335,"duration_ms":297980,"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":[{"comment":"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.","section":"§3.2, Proposition 3.5(i)"},{"comment":"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.","section":"§3.2, Proposition 3.5(iii) and §3.3, Theorem 3.7"},{"comment":"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.","section":"§3.2, Proposition 3.6"}],"minor_comments":[{"comment":"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.","section":"§4.2, Theorem 4.6"},{"comment":"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.","section":"§3.2, Proposition 3.5(iv)"},{"comment":"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.","section":"§6, Table 1"}],"recommendation":"reject","confidential_remarks":"The central theorem is false as stated; the counterexamples P5 and C5 are small and checkable by hand. This is not a matter of a missing proof or a gap in a peripheral lemma; the main equivalence and the classification of minimally γ_g-imperfect graphs are directly contradicted. The paper may reflect a systematic confusion in the values of the D-game, but I cannot confirm that. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nAlso 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.\n\nThe 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.\n\nOverall: 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.","headline":"A solid structural characterization of γ_g-perfect graphs, with one load-bearing finite check that needs to be written out.","tokens_in":16892,"tokens_out":2043,"would_cite":true,"duration_ms":19319,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C57","05C69","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Domination-game perfect graphs reduce to a recursive two-operation construction.","keywords":["domination game","game domination number","perfect graphs for domination games","hereditary graph properties","recursive characterization","recognition algorithm","cographs","total domination game"],"falsifier":"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.","tokens_in":15921,"feed_emoji":"🎮","tokens_out":6624,"duration_ms":60984,"temperature":0.7,"pith_summary":"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.","feed_headline":"One recursive rule classifies domination-game perfect graphs","feed_subtitle":"The characterization gives polynomial recognition and identifies every minimal failure.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["$\\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."],"supporting_citations":[{"why":"Introduces the domination game and defines the game domination number $\\gamma_g$, the invariant whose hereditary equality is under study.","marker":"[4]"},{"why":"Establishes standard extremal and structural properties of the domination game used in the preliminary section.","marker":"[17]"},{"why":"Supplies the characterizations of graphs with game domination number 1 or 2 that are applied throughout the case analyses.","marker":"[18]"},{"why":"Provides the characterization of cographs that underpins the classification of $\\gamma_{tg}$-perfect and $\\gamma'_{tg}$-perfect graphs.","marker":"[9]"},{"why":"Characterizes trees with trivial game domination number, used as the benchmark for the $\\gamma_g$-perfect tree corollary.","marker":"[21]"},{"why":"Introduces the total domination game and the invariants $\\gamma_{tg}$ and $\\gamma'_{tg}$ used in Section 5.","marker":"[12]"},{"why":"Supplies basic upper-bound and structural results for the total domination game needed for the total perfection proofs.","marker":"[13]"}],"fun_headline_variants":["Recursive rule classifies all domination-game perfect graphs","Polynomial recognition for perfect domination-game graphs","Minimal failures of domination games have domination number 2","Triangle-free minimal imperfects for domination games identified","Total game perfection: precisely cographs avoiding one induced subgraph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Recursive rule classifies all domination-game perfect graphs","Polynomial recognition for perfect domination-game graphs","Minimal failures of domination games have domination number 2","Triangle-free minimal imperfects for domination games identified","Total game perfection: precisely cographs avoiding one induced subgraph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002071,"raw_usage":{"total_tokens":8027,"prompt_tokens":885,"completion_tokens":7142,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":7066}},"tokens_in":501,"tokens_out":7142,"duration_ms":55844,"temperature":1.0,"reasoning_tokens":7066,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:10:49.827328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Kinnersley, D.B","cited_arxiv_id":null,"evidence_quote":"Establishes standard extremal and structural properties of the domination game used in the preliminary section."},{"cited_title":"Klavˇ zar, G","cited_arxiv_id":null,"evidence_quote":"Supplies the characterizations of graphs with game domination number 1 or 2 that are applied throughout the case analyses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the characterization of cographs that underpins the classification of $\\gamma_{tg}$-perfect and $\\gamma'_{tg}$-perfect graphs."},{"cited_title":"Nadjafi-Arani, M","cited_arxiv_id":null,"evidence_quote":"Characterizes trees with trivial game domination number, used as the benchmark for the $\\gamma_g$-perfect tree corollary."},{"cited_title":"Henning, S","cited_arxiv_id":null,"evidence_quote":"Introduces the total domination game and the invariants $\\gamma_{tg}$ and $\\gamma'_{tg}$ used in Section 5."},{"cited_title":"Henning, S","cited_arxiv_id":null,"evidence_quote":"Supplies basic upper-bound and structural results for the total domination game needed for the total perfection proofs."}],"review_version":1}