AFTD Auto-Formalizing Theoretical Domains

simple_graph_dominating_sets

def

D(G): the dominating sets of G, i.e. the finite vertex sets S such that every vertex of G lies in S or is adjacent to a vertex of S.

Statement

def simple_graph_dominating_sets {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : Finset (Finset V)
Source
step towards simple_graph_local_avg_dominating_order_stem_le
Verified
20 Oct 2026
Axioms
none listed
Used by 9

Lean source view module on GitHub

/-- The family of all dominating sets of G; `simple_graph_dominating_sets_containing G v` is the subfamily of those containing v. -/
def simple_graph_dominating_sets {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : Finset (Finset V) := Finset.univ.filter (fun S => ∀ w, w ∈ S ∨ ∃ u ∈ S, G.Adj u w)
See it in the graphDiscuss this resultChallenge it