AFTD Auto-Formalizing Theoretical Domains

simple_graph_domination_number

def

The domination number gamma(G) of a finite simple graph G is the minimum cardinality of a dominating set of G.

Statement

noncomputable def simple_graph_domination_number {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
Defined in
arXiv:2610.28936 Definition 2.1
Verified
25 Oct 2026
Axioms
none listed
Built on 1
  • simple_graph_is_dominatingA subset S of vertices in a simple graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S.
Used by 11

Read back from the Lean

For a finite type V and a simple graph G on V, simple_graph_domination_number G is the natural number defined as the infimum (sInf) of the set of all k : ℕ for which there exists a Finset V S of cardinality k such that S is a dominating set of G (according to simple_graph_is_dominating).

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

/-- The domination number of a finite simple graph. -/
noncomputable def simple_graph_domination_number {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := sInf {k : ℕ | ∃ S : Finset V, simple_graph_is_dominating G (S : Set V) ∧ S.card = k}
See it in the graphDiscuss this resultChallenge it