Pith. sign in

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 →

arxiv 2507.11194 v1 pith:CMH4NJVX submitted 2025-07-15 math.CO

classification math.CO MSC 05C6905C0505C7605A15
keywords connectedforcingzeroCF-densegraphsZTCF-densetreesgraphoperationsenumerationdensity
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

Connected forcing sets are zero forcing sets whose induced subgraph is connected, and a graph is CF-dense when every vertex belongs to at least one minimum connected forcing set. The paper introduces CF-dense graphs as a companion to the existing notions of ZF-dense and TF-dense graphs, then asks which graphs, especially trees, have this property. Its central result is a complete characterization: a tree is CF-dense exactly if it is a path on one or two vertices, or every support vertex of the tree is a strong support vertex — in plain terms, every leaf has a sibling leaf. A second main result is a closed-form formula for the number of connected forcing sets of each size in any tree. The paper also proves that several familiar families (cycles, complete graphs, wheels, hypercubes, complete multipartite graphs, diamond necklaces) are dense in the strongest combined sense, and gives conditions under which Cartesian products, joins, and coronas preserve density.

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.

Watch

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

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. [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.
  2. [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.'
  3. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities appear. The paper depends on several external theorems, mostly from the authors' own research program, which are published; one auxiliary claim is asserted without proof.

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.
    Theorem 15 and Lemma 14 of [10], cited in Section 5. Both the CF-dense tree characterization and the enumeration formula are built on it.
  • domain assumption Z(Q_k)=2^(k-1) for hypercubes.
    Cited from [34] and used in Proposition 9 to show hypercubes are ZTCF-dense.
  • domain assumption Formulas for zero forcing and total forcing numbers of joins hold under the stated connectivity conditions.
    Lemmas 27 and 28, cited from [36] and [26], used in Theorem 30.
  • domain assumption Corona zero forcing formula Z(G∘H)=qZ(H)+Z(G) for isolate-free H.
    Proposition 32, cited from [14,32], used in Lemmas 33 and 35.
  • domain assumption Adding a universal vertex to an isolate-free graph increases the zero forcing number by exactly one.
    Asserted without proof or citation in Lemma 35; needed for the lower bound of the total forcing number of coronas.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2507.11194 by the authors.

Figure 1
Figure 1. (a) A graph with a unique minimum connected forcing set (shown in blue). [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Three graphs with minimum connected forcing sets shown in blue: (a) the [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. A tree T for which zc(T; 8) is computed in Example 2. Example 2. In this example, we will apply Theorem 18 to enumerate the connected forcing sets of size d = 8 for the tree T shown in [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: All connected forcing sets of size 8 for the tree [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 35 canonical work pages

  1. [10]

    Brimkov and I

    B. Brimkov and I. V. Hicks, Complexity and computation of connected zero forcing, Discrete Appl. Math. , 229 (2017), 31–45. 23

  2. [1]

    Ackerman, O

    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

  3. [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

  4. [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

  5. [4]

    Barioli, W

    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

  6. [5]

    Ben-Zwi, D

    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

  7. [6]

    Breˇ sar, M

    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

  8. [8]

    Brimkov, R

    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

Show all 37 references
  1. [9]

    Brimkov, C

    B. Brimkov, C. C. Fast and I. V. Hicks, Graphs with Extremal Connected Forcing Numbers, arXiv:1604.00740, (2017)

  2. [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

  3. [12]

    Burgarth and V

    D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett., 99(10) (2007), 100501

  4. [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

  5. [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)

  6. [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

  7. [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

  8. [17]

    Davila, Bounding the forcing number of a graph

    R. Davila, Bounding the forcing number of a graph. Rice University, Masters The- sis, 2015

  9. [18]

    Davila, Total and zero forcing in graphs

    R. Davila, Total and zero forcing in graphs. Ph.D Thesis, University of Johannes- burg, 2019

  10. [19]

    Davila and M

    R. Davila and M. A. Henning, Matching, path covers, and total forcing sets,Quaest. Math., 43(1) (2019), 131–147

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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

  19. [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

  20. [29]

    Haynes, S

    T. Haynes, S. Hedetniemi and M. A. Henning, Domination in Graphs: Core Con- cepts (Springer Monographs in Mathematics) . (2023)

  21. [30]

    M. A. Henning and C. L¨ owenstein, Locating-total domination in claw-free cubic graphs, Discrete Math., 312 (2012), 3107–3116

  22. [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)

  23. [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)

  24. [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

  25. [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

  26. [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)

  27. [36]

    F. A. Taklimi, Zero forcing sets for graphs. University of Regina, Ph.D Thesis , 2013

  28. [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

  29. [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

Pith tools

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