REVIEW 3 major objections 4 minor 26 references
Minimal graphs with disjoint dominating and paired-dominating sets
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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).
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Observation 4.1(6)] 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.
- [Theorem 6.2, reverse direction] 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.
- [Theorem 6.1, Subcase 3.1.3] 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.
minor comments (4)
- [Theorem 6.2] 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 2] 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.
- [Observation 4.1(3)] 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 8] 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.
Circularity Check
No significant circularity; the characterization is derived self-contained from stated definitions and proved structural lemmas.
full rationale
The paper's derivation chain is self-contained. The central equivalence Theorem 3.1 is proved from Theorem 6.1, which characterizes minimal DPD P-graphs as 2-subdivision graphs with a unique DP-pair or C3/C6/C9, and Theorem 6.2, which proves that such graphs are exactly 2-subdivision graphs of isolate-free graphs with no good subgraph. The notion of a 'good subgraph' is introduced in Section 5 as an auxiliary combinatorial object with explicit degree and path-orientation conditions, not as a restatement of non-minimality. Both directions of the equivalence are then proven: a good subgraph in H yields a proper spanning DPD P-subgraph of S2(H), and a non-minimal S2(H) yields a good subgraph assembled from the components of a minimal spanning DPD P-subgraph. The cited prior work of Southey and Henning is used only for background and terminology, not as the load-bearing justification of the main theorem. Proposition 4.4, which supplies the DPD P-pair for every 2-subdivision graph, is proved directly from the definition. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' earlier papers, and no ansatz is smuggled in via citation. The skeptic's concern about the exhaustiveness of Observation 4.1(6) or the type-incoherence of the definition of v_i-tilde identifies a possible technical gap or correctness risk in the proof, but it is not circularity: a gap in a structural proof does not make the argument depend on its own conclusion.
Assumptions & free parameters
assumptions (2)
- standard math Background in finite graph theory as in Chartrand, Lesniak and Zhang [3], including standard definitions of domination, neighborhoods, and subgraphs.
- domain assumption Graphs are finite and may contain multiple edges and loops.
Cite this review
Pith. "Pith review of Minimal graphs with disjoint dominating and paired-dominating sets." pith.science (2026). https://pith.science/paper/NGW3ZPOY
@misc{pith2026190804189,
author = {Pith},
title = {Pith review of: Minimal graphs with disjoint dominating and paired-dominating sets},
year = {2026},
howpublished = {\url{https://pith.science/paper/NGW3ZPOY}},
note = {Machine review of arXiv:1908.04189}
}
abstract
A subset $D\subseteq V_G$ is a dominating set of $G$ if every vertex in $V_G-D$ has a~neighbor in $D$, while $D$ is a paired-dominating set of $G$ if $D$ is a~dominating set and the subgraph induced by $D$ contains a perfect matching. A graph $G$ is a $D\!P\!D\!P$-graph if it has a pair $(D,P)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $P$ is a paired-dominating set of $G$. The study of the $D\!P\!D\!P$-graphs was initiated by Southey and Henning (Cent. Eur. J. Math. 8 (2010) 459--467; J. Comb. Optim. 22 (2011) 217--234). In this paper, we provide conditions which ensure that a graph is a $D\!P\!D\!P$-graph. In particular, we characterize the minimal $D\!P\!D\!P$-graphs.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
V. Anusuya, R. Kala, A note on disjoint dominating sets in graphs, Int. J. Contemp. Math. Sci. 7 (2012) 2099–2110
work page 2012
- [2]
-
[3]
G. Chartrand, L. Lesniak, P. Zhang, Graphs and Digraphs . CRC Press, Boca Raton, 2016
work page 2016
-
[4]
P. Delgado, W.J. Desormeaux, T.W. Haynes, Partitioning the vertices of a graph into two total dominating sets, Quaest. Math. 39 (2016) 863–873
work page 2016
-
[5]
W.J. Desormeaux, T.W. Haynes, M.A. Henning, Partitioni ng the vertices of a cubic graph into two total dominating sets, Discrete Appl. Math. 223 (2017) 52–63
work page 2017
-
[6]
M. Dorfling, W. Goddard, J.H. Hattingh, M.A. Henning, Aug menting a graph of minimum degree 2 to have two disjoint total dominating set s, Discrete Math. 300 (2005) 82–90
work page 2005
-
[7]
T.W. Haynes, M.A. Henning, Trees with two disjoint minim um independent dominating sets, Discrete Math. 304 (2005) 69–78
work page 2005
-
[8]
S.M. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, L. Marku s, P.J. Slater, Disjoint dominating sets in graphs, Proc. ICDM 2006, Ramanujan Mathe matics Society Lect. Notes Ser. 7 (2008) 87–100
work page 2008
Show all 26 references
-
[9]
Heggernes, J.A
P. Heggernes, J.A. Telle, Partitioning graphs into gene ralized dominating sets, Nordic J. Comput. 5 (1988) 128–142
1988
-
[10]
Henning, Ch
M.A. Henning, Ch. Löwenstein, D. Rautenbach, Remarks a bout disjoint domi- nating sets, Discrete Math. 309 (2009) 6451–6458. 18
2009
-
[11]
Henning, C
M.A. Henning, C. Löwenstein, D. Rautenbach, Partition ing a graph into a dom- inating set, a total dominating set, and something else, Discuss. Math. Graph Theory 30 (2010) 563–574
2010
-
[12]
Henning, C
M.A. Henning, C. Löwenstein, D. Rautenbach, An indepen dent dominating set in the complement of a minimum dominating set of a tree, Appl. Math. Lett. 23 (2010) 79–81
2010
-
[13]
Henning, C
M.A. Henning, C. Löwenstein, D. Rautenbach, J. Southey , Disjoint dominating and total dominating sets in graphs, Discrete Appl. Math. 158 (2010) 1615–1623
2010
-
[14]
Henning, A.J
M.A. Henning, A.J. Marcon, Semitotal domination in gra phs: Partition and algorithmic results, Util. Math. 106 (2018) 165–184
2018
-
[15]
M. A. Henning, D. F. Rall, On graphs with disjoint domina ting and 2-dominating sets, Discuss. Math. Graph Theory 33 (2013) 139–146
2013
-
[16]
Henning, J
M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159–162
2008
-
[17]
Henning, J
M.A. Henning, J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009) 119–129
2009
-
[18]
Henning, A
M.A. Henning, A. Yeo, Total Domination in Graphs , Springer Monographs in Mathematics, Springer, 2013
2013
-
[19]
Kiunisala, F.P
E.M. Kiunisala, F.P. Jamil, On pairs of disjoint domina ting sets in a graph, Int. J. Math. Anal. 10 (2016) 623–637
2016
-
[20]
Kulli, S.C
V.R. Kulli, S.C. Sigarkanti, Inverse domination in gra phs, Nat. Acad. Sci. Lett. 14 (1991) 473–475
1991
-
[21]
Lowenstein, D
C. Lowenstein, D. Rautenbach, Pairs of disjoint domina ting sets and the mini- mum degree of graphs, Graphs Combin. 26 (2010) 407–424
2010
-
[22]
Miotk, J
M. Miotk, J. Topp, P. Żyliński, Disjoint dominating and 2-dominating sets in graphs, arXiv:1903.06129v1
1903 arXiv
-
[23]
Ore, Theory of Graphs , Amer
O. Ore, Theory of Graphs , Amer. Math. Soc. Colloq. Publ. 38, Amer. Math. Soc., Providence, RI, 1962
1962
-
[24]
Southey, M.A
J. Southey, M.A. Henning, Graphs with disjoint dominat ing and paired- dominating sets, Cent. Eur. J. Math. 8 (2010) 459–467
2010
-
[25]
Southey, M.A
J. Southey, M.A. Henning, Dominating and total dominat ing partitions in cubic graphs, Cent. Eur. J. Math. 9 (2011) 699–708
2011
-
[26]
Southey, M.A
J. Southey, M.A. Henning, A characterization of graphs with disjoint dominating and paired-dominating sets, J. Comb. Optim. 22 (2011) 217–234. 19
2011
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.