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
- two_token_domination_number_even_matching_leLet G be a finite simple graph on vertex type V whose complement graph Gᶜ is 1-regular. Then the domination number of the 2-token graph…
- two_token_domination_number_ge_ceil_halfLet G be a finite simple graph on vertex type V with domination number at least 2. Then the domination number of the 2-token graph F_2(G)…
- three_token_k2n_domination_number_fourThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is 4.
- three_token_star_domination_number_fourThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 4)) is 3.
- two_token_domination_number_boundLet G be a finite simple graph on vertex type V with domination number at least 2. Then the domination number of the 2-token graph F_2(G)…
- three_token_star_domination_number_threeThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is 1.
- three_token_k2n_domination_number_four_geThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at least 4.
- two_token_dominating_set_card_ge_ceil_halfLet G be a finite simple graph on vertex type V with domination number at least 2. Then every dominating set D of the 2-token graph F_2(G)…
- three_token_k2n_domination_number_four_leThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at most 4.
- three_token_star_domination_number_three_leThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is at most 1.
- two_token_domination_number_odd_p3_matching_leLet G be a finite simple graph on vertex type V whose complement graph Gᶜ has a unique vertex of degree 2 and all other vertices of degree…
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}