{"id":"d5f2e3b2-2334-492d-8457-76fbd57ab8f7","arxiv_id":"1908.04189","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A connected graph with no redundant edges that still admits a dominating set disjoint from a paired-dominating set is exactly a 2-subdivision graph of a connected graph free of isolated vertices and good subgraphs, except for cycles of length 3, 6, and 9.","lead":"The paper characterizes minimal graphs that can be split into a dominating set and a paired-dominating set. Such graphs are exactly the 2-subdivision graphs of connected graphs without isolated vertices and without a certain 'good subgraph', with short cycles as exceptions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reverse direction of Theorem 6.2 rests on an unproven component classification; a gap there would invalidate the main equivalence.","rationale":"The reader identified Observation 4.1(6) as the weakest assumption, and I agree that the component classification is the most load-bearing technical step. My concern is broader and more concrete: the reverse direction of Theorem 6.2 uses not only the classification but also a subsequent, under-specified construction of the paths P_i in H, including the type-incoherent definition of ~v_i. If either the classification is incomplete or the path construction is invalid, the equivalence between minimality of S2(H) and absence of good subgraphs in H could fail. The paper contains no machine-checked proof and no computational verification, so these steps rest entirely on the written argument. I do not claim the theorem is false; I claim the proof as written has a gap that should be fixed before the result is considered fully established. The reader's CONDITIONAL verdict appropriately reflects this. No change to the verdict is needed, but the flagged concerns should be addressed in a revision.","tokens_in":17451,"tokens_out":20671,"duration_ms":190117,"concrete_test":"Write an exhaustive checker for all connected graphs H with at most 6 vertices, allowing loops and multiple edges and no isolated vertices. For each G=S2(H), enumerate all proper spanning subgraphs G' that are themselves 2-subdivision graphs. For each such G', verify: (i) every component satisfies the dichotomy of Observation 4.1(6); (ii) if G' is a minimal DPD P-graph, the Q constructed in Theorem 6.2 is a good subgraph of H. If any instance fails, the reverse direction of Theorem 6.2 has a genuine gap. As a lighter analytical check, independently re-derive Observation 4.1(6) from the definition of S2, especially the claim that a leaf of F in V^n is not in N_G[S_G].","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central equivalence Theorem 3.1(3) depends on the reverse direction of Theorem 6.2: if S2(H) is not minimal, then H must contain a good subgraph. The proof takes a minimal spanning DPD P-subgraph G' of G=S2(H), classifies each component F of G' using Observation 4.1(6), and then assembles a good subgraph Q of H from the components whose leaves meet V^n. Two unproven assertions carry this argument. First, Observation 4.1(6), Case 2, states without real justification that a leaf x0 of F lying in V^n does not belong to N_G[S_G]; the component classification is concluded from this. If a further component type exists, the reduction to S2(P_{k+1}) fails. Second, in Theorem 6.2 the definition of ~v_i as 'the only vertex in N_G(v_i) \\ N_{G'}(v_i) ⊆ V_H' is type-incoherent: for v_i∈V_H\\L_H, all neighbors of v_i in G are subdivision vertices in V^n, not vertices of V_H. The intended construction of the oriented paths P_i in H is therefore ambiguous. Since the degree conditions (1)-(3) defining a good subgraph are verified only from the properties of these paths, a hidden assumption here would allow H to have no good subgraph while S2(H) is non-minimal, contradicting Theorem 3.1(3).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies graphs whose vertex set can be partitioned into a dominating set and a paired-dominating set, called DPDP-graphs, with emphasis on minimal such graphs. It introduces the 2-subdivision graph S2(H) of a multigraph H and a notion of a 'good subgraph' of H. The main result, Theorem 3.1, characterizes connected minimal DPDP-graphs of order at least three: they are exactly the graphs S2(H) for a connected graph H with no isolated vertices and no good subgraph, with two equivalent formulations in terms of uniqueness of the natural DP-pair and in terms of absence of proper spanning 2-subdivided subgraphs. The proof proceeds by Theorem 6.1, which handles the forward direction and the structure of minimal DPDP-graphs, and Theorem 6.2, which proves the equivalence with the absence of good subgraphs. The paper also derives corollaries for paths, cycles, trees, and iterated 2-subdivision graphs, and closes with computational open problems.","tokens_in":17749,"tokens_out":18364,"duration_ms":187199,"significance":"If the main characterization is correct, it is a substantial structural result in domination theory, extending earlier work of Southey and Henning on DPDP-graphs. The paper is self-contained, develops a concrete decomposition of minimal graphs as 2-subdivision graphs, and introduces a checkable combinatorial object (good subgraph) that is then used to characterize minimality. The application to trees and the explicit examples in Figures 2 and 3 are useful. The paper also honestly lists open algorithmic questions. However, the significance in the current form is conditional: two load-bearing parts of the proof, namely the component classification in Observation 4.1(6) and the construction of the good subgraph in the reverse direction of Theorem 6.2, are not proved with sufficient rigor, and one subcase of Theorem 6.1 is explicitly omitted.","major_comments":[{"comment":"The proof of the component classification is incomplete. In Case 2, the sentence 'Since G′ is a 2-subdivision graph, the vertex x0 does not belong to NG[SG]' is asserted without justification, yet it is the step that forces a component with a leaf in V^n_{S2(H)} to be a 2-subdivision graph of a path. The subsequent claim that a vertex of degree at least three cannot lie in V_H′, where V_H′ is written as the set {y ∈ V_F : d_F(x0,y) ≡ 0 (mod 3)}, is also not proved and uses an unexplained equality. These facts are load-bearing because Theorem 6.2 uses exactly this classification to identify the components F_i and to define the paths that later form the good subgraph. A complete proof of Observation 4.1(6) is required.","section":"Observation 4.1(6)"},{"comment":"The definition of the vertex ~v_i is not justified as written. The text says 'let ~v_i be the only vertex in NG(vi) \\ NG′(vi) ⊆ V_H', where vi is a leaf of F_i. If vi is a subdivision vertex in V^n_{S2(H)}, its missing neighbor in G could a priori be another subdivision vertex in V^n, for example when the deleted edge is the middle edge of a subdivided edge of H, rather than a vertex of V_H. The manuscript does not prove that this case cannot occur for the chosen 'farthest' leaf. Since the oriented path P_i in H is built by adding ~v_i and the edge vi~v_i, the entire verification of the degree conditions (1)–(3) for a good subgraph depends on this missing argument. This is a central gap in the reverse direction of Theorem 6.2.","section":"Theorem 6.2, reverse direction"},{"comment":"The proof of the case d_H(v) ≥ 3 explicitly omits the cases in which the three incident edges e, f, g are not all between distinct vertices: the paragraph concludes 'We derive similar contradictions if u, w, and z are not distinct ... We omit the proofs of these cases which are analogous'. Since the paper allows multiple edges and loops in H, these are not empty or purely notational cases. In particular, parallel edges can create degree-counting situations different from the three-distinct-neighbors case, and the contradiction with minimality must be checked separately. The forward direction of the characterization therefore has an unproven subcase.","section":"Theorem 6.1, Subcase 3.1.3"}],"minor_comments":[{"comment":"The symbol v_i is used both for the support vertex of F_i and for the selected leaf of F_i; this makes the definition of ~v_i very hard to parse. Rename one of them, for instance s_i for the support and x_i for the leaf.","section":"Theorem 6.2"},{"comment":"The function α is defined with codomain N, but α(v) should be a positive integer for the construction to make sense; otherwise the notation [α(v)] can be empty and leaves could disappear from S2(H). Please state that α takes values in the positive integers.","section":"Section 2"},{"comment":"The distance congruence in Observation 4.1(3) is used later to rule out two strong support vertices, but its proof is relegated to the phrase 'immediate consequences'; since it is a nontrivial structural fact, a proof or a reference would help the reader.","section":"Observation 4.1(3)"},{"comment":"The open problems ask 'How difficult is it to recognize...' without specifying the intended notion of difficulty. It would be clearer to ask whether the recognition problems are polynomial-time solvable or NP-complete.","section":"Section 8"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the main theorem is plausible, but I do not think the submitted proof is complete. The gaps in Observation 4.1(6) and in the reverse direction of Theorem 6.2 are load-bearing, and the omitted parallel-edge subcase in Theorem 6.1 should be filled. These are likely fixable with additional arguments, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper is a solid, specialized structural characterization. The main theorem—minimal DPD P-graphs are exactly S2(H) where H is connected, isolate-free, and has no 'good subgraph'—is new and, as far as I can tell, proven correctly. The good-subgraph notion is the right organizing device; it cleanly separates minimal from non-minimal cases. The corollaries for trees and corona graphs are useful. The forward direction of Theorem 6.2 is convincing.\n\nThe soft spots are concentrated in the reverse direction of Theorem 6.2 and its supporting lemma. Observation 4.1(6) classifies components of a 2-subdivision spanning subgraph, and the reverse direction leans on that classification. But one step in Case 2—'Since G′ is a 2-subdivision graph, the vertex x0 does not belong to NG[SG]'—is asserted without justification. It's load-bearing; I suspect it's true, but the proof needs to say why. The notation in Theorem 6.2 also reuses v_i for both the support vertex and the farthest leaf, which makes the definition of ~v_i look type-incoherent. The stress-test note called this an error; I think it's a typo, not a mathematical flaw, because the claim concerns the leaf's neighbors, not the support's. Still, it must be fixed. Minor: Subcase 3.1.3 of Theorem 6.1 omits several analogous cases with a hand-wave; a referee should ask for them.\n\nOverall, the central equivalence holds up. The paper is for domination theorists; outside that group it won't matter much, but inside it's a genuine advance. It deserves peer review, and a good referee can get the notation and missing justifications cleaned up.","headline":"The minimal DPD P-graph characterization is new and basically sound, but the reverse direction of Theorem 6.2 has an underexplained component-classification step and a confusing notation issue that should be fixed before acceptance.","tokens_in":18260,"tokens_out":14481,"would_cite":true,"duration_ms":138899,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"A connected graph is a minimal DPDP-graph if and only if it is the 2-subdivision graph of a connected graph with no isolated vertex and no good subgraph.","keywords":["DPDP-graph","paired domination","dominating set","2-subdivision graph","good subgraph","minimal graph","graph partition","domination"],"falsifier":"Enumerate all connected graphs $H$ on, say, at most ten vertices, test whether $H$ has no good subgraph, and then delete edges from $S_2(H)$ one at a time to check whether any proper spanning subgraph remains a DPDP-graph; the theorem predicts none. A single $H$ with no good subgraph whose $S_2(H)$ is not minimal would refute Theorem 3.1. Independently, one can search for a spanning 2-subdivision subgraph of $S_2(H)$ whose component has two strong support vertices, which would contradict Observation 4.1(6).","tokens_in":17261,"feed_emoji":"🧩","tokens_out":6794,"duration_ms":63003,"temperature":0.7,"pith_summary":"The paper characterizes the edge-minimal graphs that admit a partition of their vertex set into a dominating set and a paired-dominating set (a DPDP-pair). Its central theorem says that for connected graphs of order at least three, the minimal DPDP-graphs are exactly the 2-subdivision graphs $S_2(H)$ of connected graphs $H$ that have no isolated vertex and no 'good subgraph'; equivalently, $S_2(H)$ carries a unique DPDP-pair unless it is a cycle of length 3, 6, or 9. This gives a finite structural witness for minimality: the absence of a good subgraph in the base graph. A sympathetic reader should care because the result reduces a question about domination partitions to a checkable condition on a smaller graph, and it shows that every graph without isolated vertices is homeomorphic to a DPDP-graph, so the class is topologically universal.","feed_headline":"Minimal DPDP graphs are exactly 2-subdivision graphs","feed_subtitle":"A vertex partition into dominating and paired-dominating sets is edge-minimal precisely when the base graph has no good subgraph.","key_machinery":"The central objects are the 2-subdivision graph $S_2(H)$, built by inserting two new vertices into every edge and loop of $H$ (and, at leaves, replacing the pendant edge by several pendant copies), and the 'good subgraph' $Q$ of $H$. A good subgraph is a subgraph without isolated vertices whose complementary edges can be oriented into directed paths, one starting at each vertex of $Q$, with prescribed in- and out-degrees; its role is to encode exactly when $S_2(H)$ has a proper spanning subgraph that is still DPDP. The proof shows that if such a $Q$ exists, deleting the middle edges of the paths corresponding to $Q$ and one further edge per oriented path produces a proper spanning DPDP subgraph, so $S_2(H)$ is not minimal; conversely, any proper spanning 2-subdivision subgraph forces such a $Q$. Thus minimality is equivalent to the nonexistence of a good subgraph.","core_discovery":"Theorem 3.1 states that if $G$ is a connected graph of order at least three, the following are equivalent: (1) $G$ is a minimal DPDP-graph; (2) $G = S_2(H)$ for a connected graph $H$ and either $(V^o, V^n)$ is the unique DPDP-pair or $G$ is a cycle of length 3, 6 or 9; (3) $G = S_2(H)$ for a connected graph $H$ with no isolated vertex and no good subgraph; (4) $G = S_2(H)$ for a connected graph $H$ and no proper spanning subgraph of $G$ without isolated vertices is a 2-subdivision graph. In other words, minimality of the domination paired-domination partition is exactly captured by the base graph $H$ being free of the oriented-path obstruction called a good subgraph.","pith_inferences":["The authors leave open how hard it is to recognize graphs with good subgraphs; for trees, Proposition 7.3 suggests a direct combinatorial test, since a good subtree is exactly one whose closed neighbourhood in $H$ is a corona $Q \\circ K_1$ with no leaf neighbours, so the tree case may be polynomial.","The edge-minimal notion used here could be paired with vertex-minimality, where no induced subgraph is DPDP; the same $S_2(H)$ machinery might yield a different family, since the core proof relies on deleting single edges.","Because $S_2(H)$ is DPDP for every isolate-free $H$, minimizing the number of subdivisions needed to make a given graph DPDP, which the authors list as an open problem, could be approached by greedily subdividing edges and testing the good-subgraph condition at each step.","The good-subgraph condition resembles a path-cover problem in directed graphs; recasting it as a flow or matching problem might provide the algorithmic answers the authors ask for in Section 8."],"forward_implications":["Every connected minimal DPDP-graph of order at least three is a 2-subdivision graph, so it has a highly regular distance structure: along each subdivided edge the vertices appear in blocks of length three.","The minimal DPDP-paths are exactly $P_4, P_7, P_{10}, P_{13}$, and the minimal DPDP-cycles are exactly $C_3, C_6, C_9$.","If $H$ is a corona graph (each vertex gets at least one pendant edge), then $S_2(H)$ is always a minimal DPDP-graph; in particular $S_2(F \\circ K_1)$ is minimal for every graph $F$.","A tree $T$ is a DPDP-tree if and only if it is a spanning supergraph of $S_2(F)$ for some forest $F$ with no isolated vertices and no good subgraphs.","Every graph without isolated vertices is homeomorphic to a DPDP-graph, since $G$ is homeomorphic to $S_2(G)$ and $S_2(G)$ is DPDP by Proposition 4.4."],"supporting_citations":[{"why":"Introduced DPDP-graphs and proved that every cubic graph is a DPDP-graph; supplies the motivating notion and baseline examples.","marker":"[24]"},{"why":"Characterized DPDP-graphs and DPDP-trees using eight (four) operations on a labeled P4; the present paper extends this line to minimal DPDP-graphs.","marker":"[26]"},{"why":"Provides Ore's classical observation that every graph without isolated vertices has two disjoint dominating sets, the background for the partition problem studied here.","marker":"[23]"}],"fun_headline_variants":["Minimal DPDP graphs: 2-subdivision characterization","Edge-minimal DPDP graphs: 2-subdivision structure","Minimal DPDP graphs: a 2-subdivision rule","Minimal DPDP graphs: 2-subdivisions, plus three cycles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The characterization rests on a structural lemma about spanning 2-subdivision subgraphs: each component is either an induced subgraph or a path-like 2-subdivision graph with at most one strong support vertex; if that classification misses a shape, the equivalence between minimality and the absence of good subgraphs can fail.","fun_headline_variants_meta":{"raw":{"variants":["Minimal DPDP graphs: 2-subdivision characterization","Edge-minimal DPDP graphs: 2-subdivision structure","Minimal DPDP graphs: a 2-subdivision rule","Minimal DPDP graphs: 2-subdivisions, plus three cycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002931,"raw_usage":{"total_tokens":11129,"prompt_tokens":945,"completion_tokens":10184,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":10112}},"tokens_in":561,"tokens_out":10184,"duration_ms":74952,"temperature":1.0,"reasoning_tokens":10112,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:47:57.165204+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all connected graphs $H$ on, say, at most ten vertices, test whether $H$ has no good subgraph, and then delete edges from $S_2(H)$ one at a time to check whether any proper spanning subgraph remains a DPDP-graph; the theorem predicts none. A single $H$ with no good subgraph whose $S_2(H)$ is not minimal would refute Theorem 3.1. Independently, one can search for a spanning 2-subdivision subgraph of $S_2(H)$ whose component has two strong support vertices, which would contradict Observation 4.1(6).","supporting_citations":[{"cited_title":"Southey, M.A","cited_arxiv_id":null,"evidence_quote":"Introduced DPDP-graphs and proved that every cubic graph is a DPDP-graph; supplies the motivating notion and baseline examples."},{"cited_title":"Southey, M.A","cited_arxiv_id":null,"evidence_quote":"Characterized DPDP-graphs and DPDP-trees using eight (four) operations on a labeled P4; the present paper extends this line to minimal DPDP-graphs."},{"cited_title":"Ore, Theory of Graphs , Amer","cited_arxiv_id":null,"evidence_quote":"Provides Ore's classical observation that every graph without isolated vertices has two disjoint dominating sets, the background for the partition problem studied here."}],"review_version":1}