REVIEW 3 major objections 3 minor 37 references
Connected forcing density and related problems
T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper proves that CF-dense trees are exactly the one- and two-vertex paths and the trees in which every support vertex is a strong support vertex, and it provides a closed-form enumeration of all connected forcing sets in trees.
desk verdict New CF-density notion and tree characterization are useful, but the headline theorem is false as stated (P3 is a counterexample) and a key corona lemma rests on a false assertion. 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 load-bearing object is the M-set characterization of minimum connected forcing sets in non-path trees, taken from [10]: a set is a minimum connected forcing set exactly when it contains all vertices of R2 ∪ R3 (the vertices whose removal splits the tree in a way that makes them unavoidable) and, for every branching vertex, all but one of the bases of its pendant paths. This reduces the density question to a local choice problem: which vertices can be chosen as the excluded or included pendant-path bases. The counting formula is carried by the functions s and s′ from Definition 5, which count k-tuples of positive (respectively nonnegative) integers bounded by b1,...,bk and summing to a; these encode how many non-mandatory vertices can be placed on each pendant path group. The product structure of Theorem 18 arises because the choices at different branching vertices are independent once the total extra vertices per group are fixed.
What would settle it
Run a brute-force search over all trees with at most ten vertices: for each tree, list every minimum connected forcing set by testing all subsets under the zero-forcing color-change rule and connectedness. If any tree outside {P1,P2} has a support vertex with exactly one leaf neighbor and yet every vertex appears in some minimum connected forcing set, Theorem 16 is false; likewise, if any tree whose support vertices are all strong has a vertex excluded from every minimum connected forcing set, the theorem fails.
Extended reading notes
Core claim
The central claim is Theorem 16: a tree T is CF-dense if and only if T is P1, T is P2, or every support vertex of T has at least two leaf neighbors. In other words, apart from the two smallest paths, a tree is CF-dense exactly when no leaf is an only child of its parent. The proof works through the M-set characterization of minimum connected forcing sets in non-path trees: such a set must contain all mandatory vertices and all but one of the bases of the pendant paths attached to each branching vertex, so a vertex can be avoided by every minimum connected forcing set only if it lies on a pendant path that is not the chosen 'extra' path. The paper's companion result, Theorem 18, counts the connected forcing sets of every size in a tree by distributing the non-mandatory vertices among the groups of pendant paths attached to the branching vertices, using two integer-composition counting functions. Together these results turn tree CF-density into a linear-time local check and make the full list of minimum connected forcing sets of a tree exactly enumerable from its pendant path lengths.
Load-bearing premise
The tree results rest on the cited theorem that in any non-path tree, minimum connected forcing sets are exactly the M-sets described above; if that characterization has an unstated exception, both the CF-dense tree characterization and the enumeration formula would need revision.
Editorial extensions
If this is right
- CF-density of a tree can be checked in linear time by scanning for support vertices with exactly one leaf neighbor.
- Theorem 18 gives an exact count of connected forcing sets of every size in a tree, so in particular the number of minimum connected forcing sets is computable directly from the pendant path lengths.
- The graphs proved ZTCF-dense include cycles, complete graphs, wheels, hypercubes, complete multipartite graphs that are not stars, and diamond necklaces; diamond necklaces also show that Z(G)<Zt(G)<Zc(G) can hold inside this class.
- Under the stated equality conditions, Cartesian products, joins, and coronas of dense graphs are again dense, so the results generate infinite families of CF-dense and ZTCF-dense graphs.
- The connected forcing number of a join is min{Z(G)+|V(H)|, Z(H)+|V(G)|} and the connected forcing number of a corona is |V(G)|Z(H)+|V(G)|, formulas inherited from zero forcing numbers.
Reading between the lines
- An extension the paper leaves implicit: because the tree criterion is purely local, an analogous characterization for unicyclic or chordal graphs may hold with the same pendant-path logic, and this is directly testable by brute force on small members of those families.
- The enumeration formula's composition-counting structure suggests the count zc(T;d) could be repackaged as the coefficient of a generating function in one variable, which would give a faster way to evaluate all sizes simultaneously than the paper's per-size sum.
- The product and join preservation results are sufficient conditions; a natural question not answered here is whether equalities like Zc(G□H)=Zc(G)|V(H)| are also necessary for density to be inherited, and small Cartesian products can be checked exhaustively to test necessity.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces CF-dense graphs, in which every vertex belongs to some minimum connected forcing set, and studies their relation to the previously studied ZF-dense and TF-dense graphs. It establishes CF-density for several families (cycles, complete graphs, wheels, hypercubes, complete multipartite graphs, diamond necklaces), gives a characterization of CF-dense trees, develops a formula for the number of connected forcing sets of each size in a tree, and analyzes preservation of CF-density and ZTCF-density under Cartesian products, joins, and coronas. The paper is written in a clear, verifiable style, with explicit worked examples such as the enumeration in Example 2.
Significance. The notion of CF-density is a natural connected analogue of the existing ZF-density and TF-density concepts, and the paper provides a useful set of sufficient conditions and constructions. If corrected, the tree characterization and the tree enumeration formula would be the main contributions, complementing the earlier work on zero and total forcing density. The paper contains no fitted parameters and no circular reasoning; its arguments are mostly direct, and several proofs, such as those for the wheel, hypercube, and diamond necklace families, are checkable and correct.
major comments (3)
- [Section 5, Theorem 16] The statement is false as written. The tree P3 satisfies condition (b): its only support vertex is the center, which is adjacent to two leaves and is therefore a strong support vertex. Yet P3 is not CF-dense: its minimum connected forcing sets are exactly the two single-vertex sets consisting of one endpoint or the other, and the central vertex belongs to neither. This contradicts Proposition 10, which explicitly notes that S3 (=P3) is not CF-dense. The proof reduces the problem to M-sets via Lemma 14 and Theorem 15, which are stated for trees different from paths, so path cases are not handled. The theorem can be repaired by excluding P3, for example by adding 'and T is not P3' to condition (b), but as stated the characterization is false.
- [Section 5, Theorem 18] The displayed enumeration formula is false. For the star S4, the formula gives zc(S4;3)=0: with |I1|=3, |M|=3, and d=3, the first factor is s(2;1,1,1), which is empty because three positive integers each at most 1 cannot sum to 2. In fact, the three sets consisting of the center and any two leaves are exactly the minimum connected forcing sets, so zc(S4;3)=3. The reason for the failure is that the factor s(|Ij|-1+S'_{i,j}; [|p_l| : l∈Ij]) counts only distributions where every pendant path receives a positive number of vertices, whereas the definition of M-sets allows exactly one pendant path to be omitted. Proposition 17 shows the correct local count includes a sum over the choice of the omitted path. The formula and its proof need to be corrected.
- [Section 6.3, Lemma 35 and Theorems 37-38] The proof of Lemma 35 asserts without proof that Z(H'_i)=Z(H)+1 for H'_i=K1∨H. This fact does follow from Lemma 27 applied to the join with K1, but the justification should be stated. In addition, the proofs of Theorem 37 (third bullet) and Theorem 38 verify the arbitrary vertex v only when v lies in a copy of H; the case v∈V(G) is omitted. It is immediate because the constructed minimum sets contain all of V(G), but as written the arbitrary-vertex argument is incomplete.
minor comments (3)
- [Section 5, Theorem 18] The notation R1_3 is used in the statement but not defined in Section 2. Please define it explicitly and distinguish it from the R1 set appearing in Definition 3.
- [Section 4, Proposition 10] The sentence 'Note also that S3 is not CF-dense, since then the central vertex would not be contained in any minimum connected forcing set' is grammatically misleading; it should say 'since the central vertex is not contained in any minimum connected forcing set.'
- [Section 6.2, Lemma 29] In the final line of the proof of Lemma 29(b), the inequality Zc(G∨H) ≥ Z(G∨H) is used together with Lemma 27; please make explicit that the equality Z(G∨H)=min{Z(G)+|V(H)|, Z(H)+|V(G)|} comes from Lemma 27 so that the reader is not left to infer it.
Circularity Check
No circularity found: the tree results are derived from independent published theorems, not from the definitions or conclusions being assumed.
full rationale
The paper's central derivation chain is not circular. The CF-dense tree characterization and the connected-forcing enumeration both rest on Lemma 14 and Theorem 15, quoted from Brimkov and Hicks [10]. Although one current author overlaps with that citation, the cited M-set characterization is an externally established theorem with stated assumptions (connected graphs different from paths) and does not assume CF-density or the enumeration formula; it is therefore independent support rather than a self-referential input. Other results used in the paper, such as the zero forcing number of hypercubes [34], ZTF-density of known families [26], and join/corona formulas [14, 32, 36], are likewise external or follow directly from definitions. There are no fitted parameters, no data-dependent normalizations, and no prediction that is equivalent to its fitted input by construction. One correctness caveat is unrelated to circularity: as stated, Theorem 16 appears to overextend the non-path M-set characterization to paths, since P3 satisfies condition (b) but is not CF-dense by Proposition 10; this is a path-exception bug in the theorem statement, not a circularity in the derivation.
Assumptions & free parameters
assumptions (5)
- domain assumption M-set characterization: in a non-path tree, a set is a minimum connected forcing set iff it contains all vertices of R2(G) and R3(G) and all-but-one bases of pendant paths at every vertex of degree at least three.
- domain assumption Z(Q_k)=2^(k-1) for hypercubes.
- domain assumption Formulas for zero forcing and total forcing numbers of joins hold under the stated connectivity conditions.
- domain assumption Corona zero forcing formula Z(G∘H)=qZ(H)+Z(G) for isolate-free H.
- domain assumption Adding a universal vertex to an isolate-free graph increases the zero forcing number by exactly one.
Cite this review
Pith. "Pith review of Connected forcing density and related problems." pith.science (2026). https://pith.science/paper/CMH4NJVX
@misc{pith2026250711194,
author = {Pith},
title = {Pith review of: Connected forcing density and related problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/CMH4NJVX}},
note = {Machine review of arXiv:2507.11194}
}
read the original abstract
A connected forcing set of a graph is a zero forcing set that induces a connected subgraph. In this paper, we introduce and study CF-dense graphs -- graphs in which every vertex belongs to some minimum connected forcing set. We identify several CF-dense graph families and investigate the relationships between CF-density and analogous notions in zero forcing and total forcing. We also characterize CF-dense trees and give a formula for the number of distinct connected forcing sets in trees. Finally, we analyze when CF-density is preserved under graph operations such as Cartesian products, joins, and coronas.
Figures
Reference graph
Works this paper leans on
-
[10]
B. Brimkov and I. V. Hicks, Complexity and computation of connected zero forcing, Discrete Appl. Math. , 229 (2017), 31–45. 23
work page 2017
-
[1]
E. Ackerman, O. Ben-Zwi and G. Wolfovitz, Combinatorial model and bounds for target set selection, Theoret. Comput. Sci. , 411(44-46) (2010), 4017–4022
work page 2010
-
[2]
AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the mini- mum rank of graphs, Linear Algebra Appl., 428(7) (2008), 1628–1648
work page 2008
-
[3]
D. Amos, Y. Caro, R. Davila and R. Pepper, Upper bounds on the k-forcing number of a graph, Discrete Appl. Math. , 181 (2015), 1–10
work page 2015
-
[4]
F. Barioli, W. Barrett, S.M. Fallat, T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory , 72(2) (2013), 146–177
work page 2013
-
[5]
O. Ben-Zwi, D. Hermelin, D. Lokshtanov and I. Newman, Treewidth governs the complexity of target set selection, Discrete Optim., 8(1) (2011), 87–96
work page 2011
-
[6]
B. Breˇ sar, M. G. Cornet, T. Dravec and M. A. Henning, Bounds on zero forcing using (upper) total domination and minimum degree, Bull. Malays. Math. Sci. Soc., 47 (2024) no. 143
work page 2024
-
[8]
B. Brimkov, R. Davila, H. Schuerger and M. Young. On a conjecture of TxGraffiti: relating zero forcing and vertex covers in graphs. Discrete Appl. Math., 359 (2024), 290–302
work page 2024
Show all 37 references
-
[9]
Brimkov, C
B. Brimkov, C. C. Fast and I. V. Hicks, Graphs with Extremal Connected Forcing Numbers, arXiv:1604.00740, (2017)
2017 arXiv
-
[11]
Brueni and L.S
D.J. Brueni and L.S. Heath, The PMU placement problem, SIAM J. Discrete Math., 19(3) (2005), 744–761
2005
-
[12]
Burgarth and V
D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett., 99(10) (2007), 100501
2007
-
[13]
Burgarth, V
D. Burgarth, V. Giovannetti, L. Hogben, S. Severini and M. Young, Logic circuits from zero forcing, Nat. Comput. , 14 (2015), 485–490
2015
-
[14]
Cameron, L
T. Cameron, L. Hogben, F. Kenter, S.A. Mojalall and H. Schuerger, Forts, (frac- tional) zero forcing, and Cartesian products of graphs, arxiv:2310.17904, (2023)
2023
-
[15]
Chekuri and N
C. Chekuri and N. Korula, A graph reduction step preserving element-connectivity and applications, Automata, Languages, and Programming, (2009) 254–265
2009
-
[16]
Chiang, L.H
C.Y. Chiang, L.H. Huang, B.J. Li, J. Wu and H.G. Yeh, Some results on the target set selection problem, J. Comb. Optim. , 25(4) (2013), 702–715
2013
-
[17]
Davila, Bounding the forcing number of a graph
R. Davila, Bounding the forcing number of a graph. Rice University, Masters The- sis, 2015
2015
-
[18]
Davila, Total and zero forcing in graphs
R. Davila, Total and zero forcing in graphs. Ph.D Thesis, University of Johannes- burg, 2019
2019
-
[19]
Davila and M
R. Davila and M. A. Henning, Matching, path covers, and total forcing sets,Quaest. Math., 43(1) (2019), 131–147
2019
-
[20]
Davila and M
R. Davila and M. A. Henning, On the total forcing number of a graph, Discrete Appl. Math. , 257 (2019), 115–127
2019
-
[21]
Davila and M
R. Davila and M. A. Henning, Relating zero forcing and domination in cubic graphs, J. Comb. Optim. , 41 (2021), 553–577
2021
-
[22]
Davila and M
R. Davila and M. A. Henning, Total forcing and zero forcing in claw-free cubic graphs, Graphs Combin., 34 (2018), 1371–1384
2018
-
[23]
Davila and M
R. Davila and M. A. Henning, Total forcing versus total domination in cubic graphs, Appl. Math. Comput. , 354 (2019), 385–395
2019
-
[24]
Davila and M
R. Davila and M. A. Henning, Zero forcing in claw-free cubic graphs, Bull. Malays. Math. Sci. Soc. , 43 (2020), 673–688
2020
-
[25]
Davila, M
R. Davila, M. A. Henning, C. Magnant and R. Pepper, Bounds on the connected forcing number of a graph, Graphs Combin., 34(6) (2018), 1159–1174
2018
-
[26]
Davila, M.A
R. Davila, M.A. Henning and R. Pepper, Zero and total forcing dense graphs, Discuss. Math. Graph Theory , 43 (2023) 619–634
2023
-
[27]
Davila, H
R. Davila, H. Schuerger and B. Small, A characterization of claw-free graphs using zero forcing invariants, arxiv:2412.0343, (2024). 24
2024
-
[28]
Haynes, S
T. Haynes, S. Hedetniemi, S. Hedetniemi and M. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Math., 15(4) (2002), 519–529
2002
-
[29]
Haynes, S
T. Haynes, S. Hedetniemi and M. A. Henning, Domination in Graphs: Core Con- cepts (Springer Monographs in Mathematics) . (2023)
2023
-
[30]
M. A. Henning and C. L¨ owenstein, Locating-total domination in claw-free cubic graphs, Discrete Math., 312 (2012), 3107–3116
2012
-
[31]
Hogben, J
L. Hogben, J. C.-H. Lin and B. L. Shader, Inverse Problems and Zero Forcing for Graphs (AMS Mathematical Surveys and Monographs, 270) . (2022)
2022
-
[32]
Javaid, I
I. Javaid, I. Irshad, M. Batool and Z. Raza, On the zero forcing number of corona and lexicographic product of graphs, arxiv:1607.04071, (2016)
2016 arXiv
-
[33]
Khosravi, S
M. Khosravi, S. Rashidi and A. Sheikhhosseini, Connected zero forcing sets and connected propagation time of graphs, Trans. Comb., 9(2) (2020), 77–88
2020
-
[34]
Peters, Positive semidefinite maximum nullity and zero forcing number,Electron
T. Peters, Positive semidefinite maximum nullity and zero forcing number,Electron. J. Linear Algebra, 23 (2012), 815–830
2012
-
[35]
Schuerger, N
H. Schuerger, N. Warnberg and M. Young, Zero forcing and vertex independence number on cubic and subcubic graphs, arxiv:2410.21724, (2024)
2024 arXiv
-
[36]
F. A. Taklimi, Zero forcing sets for graphs. University of Regina, Ph.D Thesis , 2013
2013
-
[37]
Trefois and J.C
M. Trefois and J.C. Delvenne, Zero forcing number, constrained matchings and strong structural controllability, Linear Algebra Appl., 484 (2015), 199–218
2015
-
[38]
Yang, Fast-mixed searching and related problems on graphs, Theoret
B. Yang, Fast-mixed searching and related problems on graphs, Theoret. Comput. Sci., 507 (2013), 100–113. 25
2013
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.