ZeroForced
inductive
The zero forcing closure of an initial set S of blue vertices in G under the color change rule.
Statement
inductive ZeroForced {V : Type*} (G : SimpleGraph V) (S : Set V) : V → Prop
- Defined in
- arXiv:2611.11352 Section 1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Used by 16
- univ_is_zero_forcing_setThe full set of vertices of any graph G is a zero forcing set.
- tree_zero_forcing_complements_not_two_extendibleThere is a tree on nine vertices whose complements of zero forcing sets are not two-extendible.
- is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
- gt_total_forcing_poly_eqFor every integer t ≥ 24, the total forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
- star_graph_zero_forcing_poly_unimodalFor every natural number n, the complete bipartite graph K_{1, n} on Unit ⊕ Fin n has a unimodal zero forcing polynomial.
- tree_zero_forcing_poly_lower_half_monotoneFor any finite tree $T$ on a finite vertex set $V$, the coefficient of $X^i$ in the zero forcing polynomial of $T$ is less than or equal…
- is_zero_forcing_set_monoIf S is a zero forcing set of a simple graph G and S is a subset of S', then S' is also a zero forcing set of G.
- zero_forcing_root_exposed_unique_neighborIf W is fort-free and contains a root-exposed fort, there is exactly one root neighbor belonging to any root-exposed fort contained in W.
- gt_connected_forcing_poly_eqFor every integer t ≥ 24, the connected forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
- zfs_compl_iff_no_stuckFor any finite graph G and finite T, the complement V\T is a zero forcing set precisely when T contains no nonempty "stuck" subset W, i.e.…
- leaf_rich_except_zero_forcing_iffIn a graph leaf-rich away from r, a set is zero forcing exactly when it contains all but at most one leaf at each support, and either…
- tree_exposure_plain_partial_sync_counterexampleFor a rooted three-vertex path the unexposed counts at ranks zero and one are one and three, while the exposed counts at ranks zero, one…
- tree_zero_forcing_conditional_antipodal_counterexampleThere is a nine-vertex tree and disjoint fixed-white and four-element free sets for which at least one 1–3 partition gives two fort-free…
- op_1400_counterexample_order_le_eightyOpen Problem OP-1400: there exists a natural number n ≤ 80 and a simple graph G on Fin n with decidable adjacency whose zero forcing…
- zero_forcing_root_exposed_fortA white set W contains a root-exposed fort if it contains a set F not containing r such that r has a neighbor in F and every vertex other…
- zero_forcing_finset_iter_of_stableIf a finite parallel forcing iteration has stabilized, the original blue set is zero forcing exactly when the stabilized set is all…
Read back from the Lean
Given a type V, a simple graph G on V, and a subset S of V, ZeroForced G S is the inductive predicate on vertices of V defined by two rules:
1. init: If v ∈ S, then ZeroForced G S v.
2. step: If u, w : V such that ZeroForced G S u, u is adjacent to w in G, and every neighbor x of u with x ≠ w satisfies ZeroForced G S x, then ZeroForced G S w.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Inductive definition of vertices in the zero forcing closure of S. -/ inductive ZeroForced {V : Type*} (G : SimpleGraph V) (S : Set V) : V → Prop | init (v : V) : v ∈ S → ZeroForced G S v | step (u : V) (w : V) : ZeroForced G S u → G.Adj u w → (∀ x, G.Adj u x → x ≠ w → ZeroForced G S x) → ZeroForced G S w