{"id":"4f6920c5-0f77-4de0-a592-c05604cc8e5c","arxiv_id":"2411.14889","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For claw-free cubic graphs, the (p,q)-spreading number is exactly determined for all parameter pairs outside a few two-valued cases.","lead":"This paper computes the minimum size of a starting set of blue vertices that, under a two-parameter spreading rule, eventually colors every vertex of a claw-free cubic graph blue. It pins down these values for almost all parameter pairs, leaving only a few cases that can take one of two values.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 15's proof assumes a minimum vertex cover has exactly two vertices per triangle; Lemma 14 only supplies a (possibly non-minimum) vertex cover, so the proof of σ(3,1) ≤ β(G)+1 is incomplete.","rationale":"The reader flagged Lemma 13's iterative invariant as the weakest point. My concern is adjacent but more direct: even granting Lemma 13, the proof of Proposition 15 does not justify applying Lemma 14 to a minimum vertex cover. This matters because the (3,1) row of Table 1 is part of the central claim, and the proof as written gives only σ(3,1) ≤ |P|+1 for a cover P that may be larger than β(G). The gap is likely repairable: in the known necklace families, maximum independent sets can be chosen with one vertex per triangle, so the intended bound is plausible. I do not see evidence that the theorem itself is false, and the main determinations for q ≥ 2 appear well supported. The reader's CONDITIONAL verdict remains appropriate; my read does not move it. Credit is due to the paper for the clean characterizations in Theorem 18 and Proposition 11, and for the explicit open problems that acknowledge the remaining two-value ambiguities.","tokens_in":15535,"tokens_out":17045,"duration_ms":173423,"concrete_test":"Generate all connected claw-free cubic graphs up to order 22 (e.g., with nauty's geng), compute the unique Δ-D partition, and for each graph test whether there exists a maximum independent set that contains exactly one vertex from every triangle-unit. If every graph passes, the missing lemma is true and Proposition 15 is repairable; if some graph fails, compute σ(3,1) by exhaustive search on that graph to check whether the Table 1 entry β or β+1 still holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Proposition 15, P is chosen with |P| = β(G), and Lemma 14 is invoked to assume that P contains exactly two vertices from every triangle. Lemma 14 (via Lemma 13) produces an independent set with one vertex per triangle, but it is not asserted to be maximum. Its complement is a vertex cover with two vertices per triangle, yet its size need not be β(G). For a triangle-diamond necklace H2k, n = 10k and β = 6k, while the Lemma 13 construction gives an independent set of size 3k (one per diamond and one per triangle) and hence a vertex cover of size 7k. Thus the P obtained from Lemma 14 cannot replace the minimum cover P in Proposition 15. The argument would go through if every connected claw-free cubic graph has a maximum independent set containing exactly one vertex from each triangle-unit; this is a strengthening of Lemma 13/14 that is neither stated nor proved. If that strengthening fails, P ∪ {v} may have size larger than β+1 and the (3,1) row of Table 1 is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15762,"tokens_out":26146,"duration_ms":255852,"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":[{"comment":"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.","section":"Section 3, Proposition 15 proof"},{"comment":"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.","section":"Section 3, Lemma 13"},{"comment":"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.","section":"Section 4, Lemma 17"},{"comment":"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.","section":"Section 3, Proposition 15 and the preceding remark"}],"minor_comments":[{"comment":"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.","section":"Section 3, Lemma 13 proof"},{"comment":"The expression 'T′ /∈ T' should read 'T′ ∈ T'; as printed it is a typo that obscures the intended argument.","section":"Section 4, Lemma 17 proof"},{"comment":"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.","section":"Section 4, after Corollary 2"},{"comment":"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.","section":"Section 3, remark after Proposition 11"},{"comment":"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.","section":"Throughout Section 4"},{"comment":"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).","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's classification is conditional on fixing the proof gaps identified in the major comments, especially the unproved strengthening of Lemma 14 needed in Proposition 15 and the broken proof of Lemma 17. I see no circularity: the cited structural lemmas from [7], [13], and [14] are published and do not already contain the table's values. If the authors can provide a correct proof of the (3,1) upper bound and repair Lemma 17, I expect the paper to be acceptable for publication in math.CO. I would not reject on the current evidence, but the load-bearing gaps prevent acceptance now."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid, narrow paper that completes most of the (p,q)-spreading table for claw-free cubic graphs. The main new results are Theorem 18 and Proposition 11; both are worth having. But the proof of Proposition 15 has a real gap that should be fixed before the paper is accepted.\n\nWhat is new: earlier work on this class only covered zero forcing, the (1,1) case. Here the authors determine σ(3,q)=β(G) for q≥2, pin m(G,2) down to u(G) or u(G)+1 depending on whether G is a diamond necklace, and give two-valued bounds for the remaining (2,2), (2,1), and (3,1) rows. The summary table is useful and honestly flags which entries are still open. Proposition 11 and Theorem 18 are well argued; the unit-wise lower bounds from Lemma 4 are clean, and the infectious-unit construction in Theorem 18 is convincing.\n\nSoft spots, in order:\n\n1. Proposition 15. The proof takes a minimum vertex cover P of size β and says that by Lemma 14 we may assume P has exactly two vertices in every triangle. Lemma 14 only gives some vertex cover with that property, not a minimum one. In a triangle-diamond necklace the Lemma 13 construction yields an independent set of size 3k, hence a vertex cover of size 7k, while β=6k. The argument needs a strengthening: there is a maximum independent set containing exactly one vertex from each triangle-unit. That is plausible, but it is neither stated nor proved, and the (3,1) row of the table depends on it.\n\n2. Lemma 13's iterative step asserts, without proof, that after deleting a triangle the remaining graph still has no diamonds, all vertices lie in triangles, and minimum degree at least 2. These facts are true and easy to justify in a sentence or two; as written it is a minor gap.\n\n3. The sharpness claim for Proposition 15 (the H2k example) and the Figure 8 verification are each compressed to a line. The H2k argument is right but terse; Figure 8 needs a short proof.\n\nCitations are honest: the authors lean on their own prior work for the definition and on [13,14] for structural lemmas, but those are published and checkable, and the new results are not restatements.\n\nWho this is for: people working on zero forcing, bootstrap percolation, or spreading parameters on regular graphs. The class is narrow, but the completed table is a natural reference result.\n\nRecommendation: send it to a serious referee. The core results stand, and the gaps in Proposition 15 and Lemma 13 are repairable. I would ask for the Proposition 15 fix rather than reject.","headline":"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.","tokens_in":16308,"tokens_out":22344,"would_cite":true,"duration_ms":216506,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["Bootstrap percolation","Zero forcing set","k-forcing set","Spreading","Claw-free cubic graphs","(p,q)-spreading number","Triangle-diamond partition","2-percolation"],"falsifier":"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.","tokens_in":15358,"feed_emoji":"🧩","tokens_out":12873,"duration_ms":107899,"temperature":0.7,"pith_summary":"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)$.","feed_headline":"In claw-free cubic graphs, the spreading number is the block count","feed_subtitle":"Except for diamond necklaces, every non-K4 graph needs exactly one starting vertex per triangle or diamond block.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Lemma 3, the unique triangle-diamond partition defining the units counted by $u(G)$.","marker":"[14]"},{"why":"Supplies Lemma 4, the subgraph lower bound used to show every 2-percolating set contains at least one vertex from each unit.","marker":"[13]"},{"why":"Establishes the zero-forcing upper bounds for claw-free cubic graphs that appear as the $(1,1)$ row of Table 1.","marker":"[9]"},{"why":"Determines the claw-free cubic graphs attaining $Z(G)=\\alpha(G)+1$, yielding $Z(G) \\le \\alpha(G)$ for all such graphs of order at least 14.","marker":"[12]"},{"why":"Introduces the $(p,q)$-spreading model and supplies the earlier complexity and tree results that frame the invariant.","marker":"[7]"},{"why":"Provides the polynomial-time independence-number algorithm for claw-free graphs used to conclude $\\sigma_{(3,q)}$ is polynomial-time computable.","marker":"[16]"}],"fun_headline_variants":["Spreading number is the unit count (mostly)","Triangle-diamond units set the spreading number","For 2-percolation, spreading equals unit count","One per triangle or diamond: spreading rule"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Spreading number is the unit count (mostly)","Triangle-diamond units set the spreading number","For 2-percolation, spreading equals unit count","One per triangle or diamond: spreading rule"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000402,"raw_usage":{"total_tokens":2235,"prompt_tokens":1223,"completion_tokens":1012,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":839,"completion_tokens_details":{"reasoning_tokens":953}},"tokens_in":839,"tokens_out":1012,"duration_ms":10137,"temperature":1.0,"reasoning_tokens":953,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:46:00.334095+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Henning, C","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 3, the unique triangle-diamond partition defining the units counted by $u(G)$."},{"cited_title":"Hedˇ zet, M.A","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 4, the subgraph lower bound used to show every 2-percolating set contains at least one vertex from each unit."},{"cited_title":"Davila, M","cited_arxiv_id":null,"evidence_quote":"Establishes the zero-forcing upper bounds for claw-free cubic graphs that appear as the $(1,1)$ row of Table 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Determines the claw-free cubic graphs attaining $Z(G)=\\alpha(G)+1$, yielding $Z(G) \\le \\alpha(G)$ for all such graphs of order at least 14."},{"cited_title":"Breˇ sar, T","cited_arxiv_id":null,"evidence_quote":"Introduces the $(p,q)$-spreading model and supplies the earlier complexity and tree results that frame the invariant."},{"cited_title":"Minty, On maximal independent sets of vertices in claw-free graphs , J","cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time independence-number algorithm for claw-free graphs used to conclude $\\sigma_{(3,q)}$ is polynomial-time computable."}],"review_version":1}