{"id":"bebd9fef-8075-4125-b3db-9e7ba55a25e8","arxiv_id":"2607.23664","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Explicit connected subcubic and cubic graphs attain Z = α + 2, refuting the TxGraffiti conjecture that Z ≤ α + 1 for connected graphs with Δ ≤ 3.","lead":"A 24-vertex subcubic graph and a 36-vertex cubic graph are built where the zero-forcing number exceeds the independence number by two. This kills a 2017 TxGraffiti conjecture that the gap was at most one for connected graphs of maximum degree 3.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"The exact branch-fort enumeration remains the sole load-bearing computational assumption; the surrounding combinatorial reduction appears sound.","rationale":"The reader identified the correct soft spot. I do not see a more serious internal issue: the cited fort characterization applies, and the proof does not require all forts of the whole graph to decompose by branch—only that every branch-contained fort must be met, which is sufficient to derive the per-branch lower bound. Sets smaller than 3h are excluded, and the three displayed terms cover every possible size-3h or size-(3h+1) survivor. The independence-number bounds and exhibited zero-forcing sets are comparatively transparent from the triangle/branch construction, while the lower bounds are the part dependent on exhaustive search. Because the necessary independent recomputation is small—only 127 and 2,047 nonempty branch subsets, followed by a few million closure checks—the concern is readily testable and does not presently justify lowering the verdict.","tokens_in":4350,"tokens_out":3426,"duration_ms":74748,"concrete_test":"Implement a separate verifier that reconstructs one branch from the stated adjacencies, enumerates all 2^7−1 (H) or 2^11−1 (G) nonempty subsets and classifies forts directly from the definition; exhaustively recompute t, h, m_h, and m_{h+1}; regenerate the 17,712 and 3,112,960 candidates; and compute each closure with an independently written forcing engine. The lower bounds are confirmed only if the table values match and every regenerated candidate has closure smaller than V.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The counterexample depends most heavily on the lower bounds Z(H) ≥ 11 and Z(G) ≥ 17. The fort argument itself is structurally valid: every zero-forcing set meets every fort, so its intersection with a branch meets every fort contained in that branch and therefore has size at least h. Once the exact values h, m_h, and m_{h+1} are known, the candidate formula m_h^3 + 3m_h^3 + 3m_{h+1}m_h^2 exhausts all sets of sizes 3h and 3h+1: the three terms respectively account for no extra vertex, an extra triangle vertex, and an extra vertex in one chosen branch. The table arithmetic gives the stated 17,712 and 3,112,960 candidates.\n\nThus the residual weak point is not an uncovered combinatorial case, but the exactness of the finite computation. An incomplete or misclassified fort enumeration could make h, m_h, or m_{h+1} wrong; a candidate-generation error could omit a relevant set; and a closure-implementation error could incorrectly report that a genuine zero-forcing set fails. Any of these would undermine the lower bound. This is ordinary but real verification risk because the paper does not provide a hand proof of these branch statistics or a machine-checked certificate.","agreement_with_reader":"agree"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The manuscript defines a three-branch construction G(F) from a triangle and six copies of a gadget F. With F=K3 it obtains a connected subcubic graph H on 24 vertices, and with a five-vertex gadget D it obtains a connected cubic graph G on 36 vertices; both graphs are supplied in graph6 format. Explicit independent sets and zero-forcing sets establish alpha(H)>=9, alpha(G)>=15, Z(H)<=11, and Z(G)<=17. Branch-and-bound and an enumeration based on the Fast–Hicks fort characterization establish the reverse inequalities. The resulting equalities alpha(H)=9, Z(H)=11 and alpha(G)=15, Z(G)=17 give Z=alpha+2 and refute the stated TxGraffiti conjecture in both its subcubic and cubic formulations.","tokens_in":4619,"tokens_out":5038,"duration_ms":103625,"significance":"If the finite computations are accepted, the paper cleanly settles the conjecture in the negative, including the cubic version recorded in the survey's Lean appendix, and shows that the bound can fail by exactly one additional unit. The graphs are small and completely specified by graph6 strings; the upper bounds are supported by explicit witnesses; the lower bounds use a published fort characterization rather than an ad hoc criterion; and the enumeration is reproducible through a self-contained standard-library Python script. The concern about exact fort enumeration is an ordinary verification issue, not an uncovered combinatorial case: the branch searches have only 2^7 and 2^11 subsets, and the paper explains how the 17,712 and 3,112,960 surviving candidates arise. This is a concise and useful counterexample note.","major_comments":[],"minor_comments":[{"comment":"Because the theorem is computational, please include the expected output of verify_note.py, the Python version used, and a checksum or persistent archive reference for the script and the two .g6 files. This would make the already reproducible lower-bound computation easier to audit.","section":"§3, verification discussion"},{"comment":"The statement that branch and bound 'terminates immediately' is too informal for the upper bounds alpha(H)<=9 and alpha(G)<=15. A sentence identifying the branching order and bound used, or the corresponding function in verify_note.py, would make this part independently intelligible without first reading the code.","section":"§3, independence-number computation"},{"comment":"The displayed candidate formula counts only sets of sizes 3h and 3h+1, although the preceding sentence says 'at most 3h+1.' Add the explicit observation that smaller sets are already excluded because they must contain at least h vertices from each of the three branches.","section":"§3, candidate-count formula"},{"comment":"Reference [1] is the 2025 survey recording the conjecture. If a distinct 2017 TxGraffiti source or conjecture number is available, it should also be cited for priority and ease of retrieval.","section":"§1 and References"}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The paper does exactly what the title says: it hands you two small explicit graphs (H on 24 vertices, Δ ≤ 3; G cubic on 36) with Z = α+2, so the 2017 conjecture is dead in both the textual and the Lean-cubic readings. That is the whole contribution, and it is real.\n\nWhat works well is the construction and the witnesses. The three-branch skeleton with two simple gadgets is easy to draw and easy to check by hand for the upper bounds and the independence numbers; the explicit blue sets and independent sets are written down. The fort reduction is standard and correctly applied: once you accept the branch statistics, the candidate counts follow by elementary casework and the exhaustive check is finite and modest. Shipping pure-Python verification code that rebuilds the graphs from the description and certifies all four numbers is the right way to handle a computational lower bound of this size. Citations are tight and on-point.\n\nThe only soft spot is exactly the one the stress-test flags: the lower bounds rest on the completeness of the fort enumeration inside a single branch and on the correctness of the subsequent exhaustive closure checks (17k sets for H, 3M for G). There is no hand proof of those branch numbers and no machine-checked certificate, only the script and the author’s claim of independent re-execution. That is ordinary verification risk for a short note of this type, not a structural hole; anyone who cares can re-run or re-implement in an afternoon. Nothing else is load-bearing.\n\nThis is for people who work on zero forcing, power domination, or the TxGraffiti conjectures. It does not reorganize the area, but it settles a concrete open claim and supplies the first cubic examples with gap 2. I would bring it to reading group as a quick “here is how the conjecture dies” item, cite it when the bound comes up, and send it to referees without hesitation. Short, clear, reproducible counterexample notes are what the literature needs.","headline":"Clean finite counterexamples that kill the TxGraffiti Z ≤ α+1 conjecture for both subcubic and cubic graphs, with the gap-2 value attained and a shipped verification script.","tokens_in":5613,"tokens_out":540,"would_cite":true,"duration_ms":11755,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C50"],"pacs":[],"model":"grok-4.5","headline":"A connected subcubic graph on 24 vertices and a cubic graph on 36 vertices both satisfy Z = α + 2, refuting the conjecture that Z ≤ α + 1.","keywords":["zero forcing number","independence number","cubic graph","subcubic graph","TxGraffiti","fort","counterexample"],"falsifier":"Re-run the accompanying verification script, or independently search for a zero-forcing set of size 10 in the 24-vertex graph or size 16 in the 36-vertex graph; any such set would collapse the claimed values of Z.","tokens_in":5529,"feed_emoji":"🔢","tokens_out":955,"duration_ms":19223,"temperature":0.7,"pith_summary":"The paper builds two explicit connected graphs of maximum degree 3 whose zero forcing number is two larger than their independence number. One is a 24-vertex subcubic graph with α = 9 and Z = 11; the other is a 36-vertex cubic graph with α = 15 and Z = 17. Both are obtained from the same skeleton—a triangle with three bridges into identical branches—by attaching a small gadget at each branch tip. The constructions falsify a 2017 conjecture that every connected graph of maximum degree at most 3 (other than K4) satisfies Z ≤ α + 1, and they falsify the cubic-only version of the same claim. A sympathetic reader cares because the bound was believed to hold for all such graphs and had already been proved for large subclasses; these examples show the gap can reach 2 and that no universal +1 bound exists even among cubic graphs.","feed_headline":"Cubic graphs can need two extra zero-forcing vertices","feed_subtitle":"Explicit 24- and 36-vertex examples kill the conjecture that Z is at most α + 1","key_machinery":"The gadget construction G(F): start with a triangle, attach three bridge vertices, and hang two copies of a degree-bounded gadget F from each bridge. Independence numbers are read off by taking a maximum independent set branch by branch; upper bounds on Z come from explicit forcing sets; lower bounds come from enumerating forts inside each branch and exhaustively checking that every set meeting all forts and of size at most 3h + 1 fails to force.","core_discovery":"There exist a connected graph H on 24 vertices with Δ(H) ≤ 3, independence number 9 and zero forcing number 11, and a connected cubic graph G on 36 vertices with independence number 15 and zero forcing number 17. Consequently Z = α + 2 is attained, the conjecture Z ≤ α + 1 fails for both subcubic and cubic connected graphs, and Z ≤ α + 1 is not a universal bound for connected cubic graphs.","pith_inferences":["Because the construction is built from identical branches joined by bridges, the same pattern can be iterated to produce infinite families with Z − α ≥ 2, which the author defers to a companion paper.","The fort-based counting argument suggests that the gap Z − α is controlled by the fort-hitting number of a single branch; altering the gadget may systematically raise or lower that gap.","A natural next check is whether every 2-connected or 3-connected cubic counter-example requires substantially more vertices than the bridged examples given here."],"forward_implications":["The conjectured bound Z ≤ α + 1 is false for connected graphs of maximum degree 3 and already fails on 24 vertices.","The same bound is false for connected cubic graphs; the smallest cubic counter-example supplied has 36 vertices.","The value Z = α + 2 is attained by both a subcubic and a cubic connected graph.","Any repaired conjecture must either exclude bridges, raise the additive constant, or impose further structural hypotheses such as claw-freeness or bridgelessness."],"fun_headline_variants":["24-vertex subcubic graph hits Z=α+2","Cubic counterexample: Z reaches α+2","Conjecture fails: Z can equal α+2","Explicit graphs refute Z≤α+1 bound","Zero forcing exceeds α by 2 in cubics"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The lower bounds rest entirely on a finite computer search that claims to have enumerated every fort inside a branch and verified that none of the surviving candidate sets of size at most 10 (respectively 16) is a zero-forcing set.","fun_headline_variants_meta":{"raw":{"variants":["24-vertex subcubic graph hits Z=α+2","Cubic counterexample: Z reaches α+2","Conjecture fails: Z can equal α+2","Explicit graphs refute Z≤α+1 bound","Zero forcing exceeds α by 2 in cubics"]},"model":"grok-4.5","effort":"low","cost_usd":0.004518,"raw_usage":{"total_tokens":1246,"prompt_tokens":685,"num_sources_used":0,"completion_tokens":64,"cost_in_usd_ticks":45184000,"prompt_tokens_details":{"text_tokens":685,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":497,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":685,"tokens_out":64,"duration_ms":8430,"temperature":1.0,"reasoning_tokens":497,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T16:22:46.659875+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Re-run the accompanying verification script, or independently search for a zero-forcing set of size 10 in the 24-vertex graph or size 16 in the 36-vertex graph; any such set would collapse the claimed values of Z.","supporting_citations":[],"review_version":1}