Pith. sign in

REVIEW 4 major objections 6 minor 17 references

Spreading in claw-free cubic graphs

T0 review · 4 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every connected claw-free cubic graph except $K_4$, the $(p,q)$-spreading number is determined exactly or narrowed to two consecutive values, and 2-percolation equals the graph's number of triangle/diamond building blocks except in…

desk verdict Solid extension of spreading numbers on claw-free cubic graphs, but the (3,1) upper bound has a proof gap that needs a fix before acceptance. read the letter →

arxiv 2411.14889 v2 pith:ZATTQXYB submitted 2024-11-22 math.CO

Boštjan Brešar , Jaka Hedžet , Michael A. Henning This is my paper · ORCID
classification math.CO MSC 05C3505C75
keywords BootstrappercolationZeroforcingsetk-forcingSpreadingClaw-freecubicgraphs(pq)-spreadingnumberTriangle-diamondpartition2-percolation
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

This paper asks how many initially blue vertices are needed to turn a whole claw-free cubic graph blue under the $(p,q)$-spreading rule, a dynamic coloring rule that generalizes zero forcing, $k$-forcing, and bootstrap percolation. Its main thesis is that for this graph family the answer is controlled almost entirely by a unique decomposition into elementary blocks: triangles and diamonds. The paper determines the $(3,q)$-spreading number exactly for every $q \ge 2$, showing it equals the minimum vertex cover size $\beta(G)$, and determines the 2-percolation number exactly: $u(G)+1$ when the graph is a diamond necklace, $u(G)$ otherwise, where $u(G)$ is the number of blocks in the decomposition. For the nontrivial cases that remain, $(p,q) = (2,1)$, $(2,2)$, and $(3,1)$, it shows the number always lies in a two-element set, leaving only the boundary between the two values open. If correct, this gives a nearly complete table of spreading numbers for a natural infinite family of cubic graphs, with exact expressions in terms of three basic parameters: $\alpha(G)$, $\beta(G)$, and $u(G)$.

What carries the argument

The central object is the triangle-diamond partition: the unique partition of $V(G)$ into sets inducing either a triangle $K_3$ or a diamond $K_4 - e$, guaranteed for every connected claw-free cubic graph other than $K_4$ by Lemma 3. Call each part a unit and let $u(G)$ be their number. Two facts make the partition the engine of the argument. First, Lemma 4 implies any 2-percolating set must contain at least one vertex from each unit, and if it contains exactly one vertex from a diamond-unit that vertex must be a dominating vertex of the diamond; this gives the lower bound $m(G,2) \ge u(G)$. Second, Observation 2 shows that once a unit is fully infected, an adjacent unit becomes fully infected as soon as one carefully chosen second vertex in it is also infected; so a set with one vertex per unit can drive the infection through the whole graph. The diamond-necklace $N_k$ is the one obstruction: there, a one-vertex-per-unit set is too sparse and a second vertex is genuinely required.

What would settle it

Run an exhaustive search over all connected claw-free cubic graphs up to, say, 24 vertices: compute by brute force whether each non-necklace graph has a 2-percolating set of size $u(G)$, and whether each graph has an independent set meeting every triangle; a single graph failing either test would refute Theorem 18 or Lemma 13, respectively.

Watch

Extended reading notes

Core claim

The core discovery is a structural reduction: in a connected claw-free cubic graph $G \ne K_4$, the $(p,q)$-spreading number is determined, up to a two-element ambiguity, by the graph's unique partition into triangle-units and diamond-units. Theorem 18 is the load-bearing result: for 2-percolation, $m(G,2) = u(G)+1$ if $G$ is a diamond necklace $N_k$ and $m(G,2) = u(G)$ otherwise. The upper direction is proved constructively: starting from a carefully chosen triangle-unit, one adds one vertex from each neighboring unit and shows, unit by unit, that infection spreads across the whole graph; the lower direction comes from the observation that every 2-percolating set must contain at least one vertex from every unit. The paper also proves $\sigma_{(3,q)}(G) = \beta(G)$ for $q \ge 2$ by identifying 3-percolating sets with vertex covers, and bounds $\sigma_{(3,1)}(G) \le \beta(G)+1$, $\sigma_{(2,2)}(G) \in \{u(G), u(G)+1\}$, and $\sigma_{(2,1)}(G) \in \{u(G)+1, u(G)+2\}$. Together these fill every row of the $(p,q)$ table except the $(1,1)$ zero-forcing row, which retains previously known upper bounds.

Load-bearing premise

The proof of Lemma 13 assumes that the iterative deletion process—remove a diamond, then keep deleting a degree-2 vertex together with its triangle—always leaves every remaining component with no diamonds, every vertex in a triangle, and minimum degree at least two; if this invariant ever fails, the existence of an independent set meeting every triangle is no longer guaranteed.

Editorial extensions

If this is right

  • For every claw-free cubic graph other than $K_4$, the 2-percolation number is either $u(G)$ or $u(G)+1$, with the larger value occurring exactly for diamond necklaces, so the number is read directly from the unit count and one structural bit.
  • For $q \ge 2$, the $(3,q)$-spreading number equals the minimum vertex cover size $\beta(G)$; since independence numbers in claw-free graphs can be computed in polynomial time, these spreading numbers are polynomial-time computable.
  • The $(2,2)$- and $(2,1)$-spreading numbers are always within one (respectively two) of $u(G)$: $u(G) \le \sigma_{(2,2)}(G) \le u(G)+1$ and $u(G)+1 \le \sigma_{(2,1)}(G) \le u(G)+2$.
  • Apart from the $(1,1)$ zero-forcing row, which inherits earlier upper bounds, the only unresolved values in the $(p,q)$ table are the choices between the two consecutive candidates in the $(2,1)$, $(2,2)$, and $(3,1)$ rows.
  • Because the $(2,q)$ values for $q \ge 3$ reduce to counting units, $\sigma_{(2,q)}$ is also determined in polynomial time for claw-free cubic graphs.

Reading between the lines

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

  • A natural next step, which the paper explicitly leaves open, is to characterize which graphs attain the lower versus upper values for $(2,2)$, $(2,1)$, and $(3,1)$; the proofs suggest the boundary is a local adjacency pattern among first-step units rather than a global invariant.
  • The exact rows of Table 1 rest only on the unit partition and on Lemma 4, while only the $(3,1)$ upper bound relies on the triangle-hitting independent set of Lemma 13; a counterexample to that lemma would therefore not disturb the main 2-percolation and 3-percolation results.
  • The unit-walking construction is effectively an algorithm: for claw-free cubic graphs it builds a minimum 2-percolating set directly, and deciding whether the graph is a diamond necklace is immediate from the partition.
  • Computing $\sigma_{(2,2)}$ and $\sigma_{(2,1)}$ by brute force for all connected claw-free cubic graphs up to a modest order would generate the data needed to conjecture the missing characterizations posed in the paper's open problems.
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

4 major / 6 minor

Summary. The paper studies the (p,q)-spreading number, a common generalization of k-forcing and r-bootstrap percolation, for connected claw-free cubic graphs. It uses the unique triangle-diamond partition of such graphs (Lemma 3) and proves that, for every pair (p,q) except (1,1), the value of sigma_{(p,q)}(G) is either determined exactly or shown to lie in a two-element set. The main new results are: sigma_{(3,q)}(G)=beta(G) for all q>=2 (Proposition 11); sigma_{(3,1)}(G)<=beta(G)+1 with a sharpness claim (Proposition 15); the exact 2-bootstrap percolation number m(G,2)=u(G)+1 for diamond necklaces and m(G,2)=u(G) otherwise (Theorem 18); and two-value bounds for sigma_{(2,2)} and sigma_{(2,1)}. The results are summarized in Table 1.

Significance. If the proofs are repaired, this is a valuable contribution: it gives a nearly complete determination of a two-parameter dynamic coloring process on a natural and well-studied graph class, unifying zero forcing, k-forcing, and bootstrap percolation. The clean determination of the 2-bootstrap percolation number of all connected claw-free cubic graphs (Theorem 18) and the elegant proof of sigma_{(3,q)}=beta(G) for q>=2 (Proposition 11) are significant. The lower-bound technique via Lemma 4 is simple and effective. The paper also correctly identifies polynomial-time computability of sigma_{(3,q)} for q>=2 and sigma_{(2,q)} for q>=3 in this graph class.

major comments (4)
  1. [Section 3, Proposition 15 proof] The proof chooses P with |P|=beta(G) and then states 'due to Lemma 14 we may assume that P contains exactly two vertices from every triangle in G'. Lemma 14 only provides some vertex cover with that property, not necessarily a minimum one; for H_{2k} the Lemma 13 construction gives an independent set of size 3k and hence a vertex cover of size 7k, whereas n=10k and beta(G)=6k. The subsequent infection argument, in particular the claim that a white vertex u adjacent to exactly one vertex of an infected triangle becomes infected, implicitly requires that every white vertex already has two blue neighbors in its own triangle, which is exactly the unproved strengthening. Please prove that there exists a minimum vertex cover (equivalently, a maximum independent set) containing exactly two vertices from every triangle, or supply a different argument for sigma_{(3,1)}(G)<=beta(G)+1.
  2. [Section 3, Lemma 13] The iterative construction in Lemma 13 asserts that after selecting a degree-2 vertex u1 and deleting its triangle, the remaining graph G2 'once again' has properties (1), (2), and (3): no diamond, every vertex in a triangle, and minimum degree at least 2. This invariant is stated without proof. In particular, after a triangle-unit is deleted, adjacent triangle-units lose an external neighbor, and it is not shown that every remaining component still satisfies the three properties. Lemma 14 and Proposition 15 depend directly on Lemma 13, so a complete proof of the invariant is needed.
  3. [Section 4, Lemma 17] The proof of Lemma 17 is not logically coherent. It supposes, toward a contradiction, that G-T has three components for every triangle-unit T. It then asserts the existence of a triangle-unit T1 for which at least one component of G-T1 contains no triangle-unit, without justifying why such T1 must exist under the supposition. The final sentence 'Therefore G1 contains a triangle-unit T' ... which is the final contradiction' does not contradict the supposition. Since Lemma 17 is used to choose the initial triangle-unit in the proof of Theorem 18, the proof of the main 2-percolation result is incomplete as written.
  4. [Section 3, Proposition 15 and the preceding remark] The sharpness assertion of Proposition 15 is not established. The remark before the proposition claims sigma_{(3,1)}(G)>beta(G) for G in Hcubic, but it only argues that no vertex cover P can be a (3,1)-spreading set; a (3,1)-spreading set of size beta need not be a vertex cover. Moreover, the sentence 'in any vertex cover P of G, every vertex in P has a neighbor in P, and so it does not have at most one neighbor in V(G)\P' does not logically follow, since having a neighbor in P does not by itself preclude having at most one neighbor outside P. Thus both the lower bound and the claimed sharpness for Hcubic require additional argument.
minor comments (6)
  1. [Section 3, Lemma 13 proof] The notation is inconsistent: the proof refers to G' in one sentence and then to G1 and G2; please unify the names of the graphs obtained after deleting diamond-units and after deleting triangle-units.
  2. [Section 4, Lemma 17 proof] The expression 'T′ /∈ T' should read 'T′ ∈ T'; as printed it is a typo that obscures the intended argument.
  3. [Section 4, after Corollary 2] The claim about Figure 8 that sigma_{(2,2)}(G)=u(G)+1 is asserted with 'one can verify'; since this example is used to show that equality of sigma_{(2,2)} and sigma_{(2,3)} does not hold in general, a proof or a more detailed certificate should be provided.
  4. [Section 3, remark after Proposition 11] The sentence 'in any vertex cover P of G, every vertex in P has a neighbor in P, and so it does not have at most one neighbor in V(G)\P' is logically incomplete; the implication should be stated precisely or replaced with a direct argument.
  5. [Throughout Section 4] There are several typos of the form 'an 2-percolating set' in Propositions 16, 19, and 20, and '|S| ≥u(G)' appears in Proposition 16 without a space; these should be corrected.
  6. [Table 1] The (1,1) entry '≤ α(G)(+1), n≥14 [Thm 2] ([Thm 1])' is hard to parse; please clarify that the bound depends on the order of G (the stronger bound holds for n at least 14, and the weaker bound holds in general).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the (p,q)-spreading values are derived from independent structural lemmas and prior published results, not from the target table.

full rationale

The derivation chain is self-contained relative to external, checkable results. The concept of (p,q)-spreading is a definition, not a fitted input; reference [7] introduced the concept, but the present paper does not rely on [7] for any numerical entry except terminology. The triangle-diamond partition (Lemma 3) is cited to [14], a published structural theorem by one coauthor; it is independent of the spreading-number claims and is used only to define units. Lemma 4 is cited to [13] and follows directly from the percolation rule; Proposition 5 then derives m(G,3)=β(G) from it without assuming the conclusion. Proposition 11 extends this to q=2 by a direct argument that every vertex of a minimum vertex cover has a neighbor in the cover, so the extension does not restate the result. Theorem 18 constructs explicit 2-percolating sets of size u(G) and proves the matching lower bound via Lemma 4; the values are not fitted. The remaining two-value bounds follow from Observation 1 and explicit constructions, not from the quantities being determined. The only conspicuous issue is in Proposition 15, where Lemma 14 supplies a vertex cover with exactly two vertices in every triangle but does not show that this cover is minimum, while the proof later assumes that the chosen minimum cover has that property. This is an apparent proof gap, hence a correctness concern, not circularity: it does not define the conclusion into the hypothesis or fit the data to the answer. Self-citations appear, but they point to published, checkable theorems whose assumptions do not include the target results, so the independence of the central derivation is preserved.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters or invented entities appear: the work is pure graph theory. The listed axioms are external structural facts with cited sources, and the central table is a new calculation built on top of them.

assumptions (6)
  • domain assumption Unique triangle-diamond partition (Lemma 3, cited to [14])
    Used throughout Sections 3 and 4 to define units and the parameter u(G); if this partition were not unique or did not exist, the unit-based formulas would be undefined.
  • domain assumption Trapping lemma (Lemma 4, cited to [13])
    Used in Propositions 5, 16, Theorem 18, and Theorem 21 to force at least one starting vertex in each unit and to establish lower bounds such as m(G,2) at least u(G).
  • standard math Brooks' coloring theorem (Theorem 6)
    Used in Theorem 7 to derive the independence lower bound n/Delta, which feeds into the bounds of Theorem 10.
  • domain assumption Independence upper bound for claw-free graphs (Theorem 8, cited to [17,10])
    Used in Theorem 9 to get alpha(G) at most (2/(delta+2))n, from which Theorem 10 derives the 3-percolation bounds.
  • standard math Gallai theorem alpha(G)+beta(G)=n(G)
    Used in Proposition 5 to convert the vertex-cover characterization into m(G,r)=n-alpha(G).
  • domain assumption Zero-forcing bounds from [9] and [12] (Theorems 1 and 2)
    Consulted rather than reproved to supply the (1,1) row of Table 1; these are published results, one by a coauthor, and they do not feed into the new (2,q) and (3,q) derivations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Spreading in claw-free cubic graphs." pith.science (2026). https://pith.science/paper/ZATTQXYB

@misc{pith2026241114889,
  author       = {Pith},
  title        = {Pith review of: Spreading in claw-free cubic graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZATTQXYB}},
  note         = {Machine review of arXiv:2411.14889}
}
abstract

Let $p \in \mathbb{N}$ and $q \in \mathbb{N} \cup \lbrace \infty \rbrace$. We study a dynamic coloring of the vertices of a graph $G$ that starts with an initial subset $S$ of blue vertices, with all remaining vertices colored white. If a white vertex~$v$ has at least~$p$ blue neighbors and at least one of these blue neighbors of~$v$ has at most~$q$ white neighbors, then by the spreading color change rule the vertex~$v$ is recolored blue. The initial set $S$ of blue vertices is a $(p,q)$-spreading set for $G$ if by repeatedly applying the spreading color change rule all the vertices of $G$ are eventually colored blue. The $(p,q)$-spreading set is a generalization of the well-studied concepts of $k$-forcing and $r$-percolating sets in graphs. For $q \ge 2$, a $(1,q)$-spreading set is exactly a $q$-forcing set, and the $(1,1)$-spreading set is a $1$-forcing set (also called a zero forcing set), while for $q = \infty$, a $(p,\infty)$-spreading set is exactly a $p$-percolating set. The $(p,q)$-spreading number, $\sigma_{(p,q)}(G)$, of $G$ is the minimum cardinality of a $(p,q)$-spreading set. In this paper, we study $(p,q)$-spreading in claw-free cubic graphs. While the zero-forcing number of claw-free cubic graphs was studied earlier, for each pair of values $p$ and $q$ that are not both $1$ we either determine the $(p,q)$-spreading number of a claw-free cubic graph $G$ or show that $\sigma_{(p,q)}(G)$ attains one of two possible values.

Figures

Figures reproduced from arXiv: 2411.14889 by the authors.

Figure 1
Figure 1. A diamond-necklace N4 For k ≥ 1 an integer, let F2k be the connected cubic graph constructed as follows. Take 2k disjoint copies T1, T2, . . . , T2k of a triangle, where V (Ti) = {xi , yi , zi} for i ∈ [2k]. Let Ea = {x2i−1x2i : i ∈ [k]} Eb = {y2i−1y2i : i ∈ [k]} Ec = {z2iz2i+1 : i ∈ [k]}, where addition is taken modulo 2k (and so, z1 = z2k+1). Let F2k be obtained from the disjoint union of these 2k triangles by add… view at source ↗
Figure 2
Figure 2. x1 y1 z1 y2 z2 x2 x3 y3 z3 y4 z4 x4 x5 y5 z5 y6 z6 x6 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The triangle-diamond-necklace H6 3 3-Percolation in claw-free, cubic graphs In this section, we study 3-percolation in claw-free, cubic graphs. The following lemma is already known in the literature and follows readily from the definition of r-bootstrap percolation. Lemma 4 ([13]) For r ≥ 2 if H is a subgraph of a graph G such that every vertex in H has strictly less than r neighbors in G that belong to V (G) \ V (H… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: A β-set in a triangle-necklace F6 Suppose next that G ∈ Hcubic. Thus, G is a triangle-diamond-necklace H2k for some k ≥ 2, and so G has order n = 10k. We can choose an independent set of G to contain one vertex from every triangle-unit and two vertices from every diamo…
Figure 5
Figure 5. Figure 5: A β-set in a triangle-diamond-necklace H6 Note that m(G, 3) in (claw-free) cubic graphs coincides with σ(3,q) (G) for all q ≥ 3, establishing the (3, 3)-entry of [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: A diamond-necklace N4 and a 2-percolating set of size 5 If two distinct units are joined by at least two edges, then we say that these two units are double￾bonded. Lemma 17 If G ̸= K4 is a connected, claw-free, cubic graph and G /∈ Ncubic, then there exists a triangle-…
Figure 7
Figure 7. Figure 7: Possible adjacent units in the proof of Theorem 18 [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: A graph G with σ(2, 3) = u(G) and σ(2, 2) = u(G) + 1 Finally, we consider (2, 1)-spreading, and bound the corresponding invariant in claw-free cubic graphs. Again we see that it can achieve only two possible values. Theorem 21 If G ̸= K4 is a connected, claw-free, cubi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    428 (2008), 1628–1648

    AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 (2008), 1628–1648

    work page 2008

  2. [2]

    D. Amos, Y. Caro, R. Davila, R. Pepper, Upper bounds on the k-forcing number of a graph , Discrete Appl. Math. 181 (2015), 1–10

    work page 2015

  3. [3]

    Babikir and M.A

    A. Babikir and M.A. Henning, Triangles and (total) domination in subcubic graphs , Graphs Combin. 38 (2022), Paper No. 28, 17 pp. 16

    work page 2022

  4. [4]

    Babikir and M.A

    A. Babikir and M.A. Henning, Upper total domination in claw-free cubic graphs, Graphs Combin. 38 (2022), Paper No. 172, 15 pp

    work page 2022

  5. [5]

    Balogh, G

    J. Balogh, G. Pete, Random disease on the square grid , Random Str. Alg. 13 (1998), 409–422

    work page 1998

  6. [6]

    Bollob´ as,The Art of Mathematics: Coffee Time in Memphis , Cambridge Univ

    B. Bollob´ as,The Art of Mathematics: Coffee Time in Memphis , Cambridge Univ. Press, New York, 2006

    work page 2006

  7. [7]

    Breˇ sar, T

    B. Breˇ sar, T. Dravec, A. Erey, J. Hedˇ zet,Spreading in graphs, Discrete Appl. Math. 353 (2024), 139–150

    work page 2024

  8. [8]

    Chalupa, P.L

    J. Chalupa, P.L. Leath, G.R. Reich, Bootstrap percolation on a Bethe lattice, J. Physics C: Solid State Physics 12 (1979), L31

    work page 1979

Show all 17 references
  1. [9]

    Davila, M

    R. Davila, M. A. Henning, Zero forcing in claw-free cubic graphs , Bull. Malays. Math. Sci. Soc. 43 (2020), 673–688

    2020

  2. [10]

    Faudree, R.J

    R.J. Faudree, R.J. Gould, M.S. Jacobson, L.M. Lesniak, T.E. Lindquester, On independent generalized degrees and independence numbers inK(1, m)-free graphs, Discrete Math. 103 (1992), 17–24

    1992

  3. [11]

    Haynes, S.T

    T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in Graphs: Core Concepts , Series: Springer Monographs in Mathematics, Springer, Cham, 2023

    2023

  4. [12]

    M. He, H. Li, N. Song, S. Ji, The zero forcing number of claw-free cubic graphs , Discrete Appl. Math. 359 (2024), 321–330

    2024

  5. [13]

    Hedˇ zet, M.A

    J. Hedˇ zet, M.A. Henning, 3-neighbor bootstrap percolation on grids, Discuss. Math. Graph Theory 45 (2025), 283–310

    2025

  6. [14]

    Henning, C

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

    2012

  7. [15]

    Hogben, J.C.-H

    L. Hogben, J.C.-H. Lin, B.L. Shader, Inverse problems and zero forcing for graphs, Mathematical Surveys and Monographs 270, American Mathematical Society, Providence, 2022

    2022

  8. [16]

    Minty, On maximal independent sets of vertices in claw-free graphs , J

    G.J. Minty, On maximal independent sets of vertices in claw-free graphs , J. Combin. Theory Ser. B 28 (1980), 284–304

    1980

  9. [17]

    H. Li, C. Virlouvet, Neighborhood conditions for claw-free Hamiltonian graphs , Twelfth British Combinatorial Conference (Norwich, 1989), Ars Combin. 29 (1990), 109–116. 17

    1990

Pith tools

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