simple_graph_is_dominating
def
A 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.
Statement
def simple_graph_is_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
- Defined in
- arXiv:2610.28936 Definition 2.1
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 15
- 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…
- simple_graph_domination_numberThe domination number gamma(G) of a finite simple graph G is the minimum cardinality of a dominating set of G.
- three_token_k2n_assemble_layer_coverIf the explicit candidate family has the claimed cardinality and dominates every configuration in each of the three possible left-token…
- 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_star_domination_number_fourThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 4)) is 3.
- not_is_pk_free_claw_free_hole_dominatingThe statement
is_pk_free_claw_free_hole_dominatingis false: The statement is false as written: it allows k = 4 and m = 3 (since k - 1 =… - simple_graph_is_dominating_univIn any simple graph G, the entire vertex set is a dominating set.
- three_token_k2n_assemble_three_layersIf the explicit candidate family has the claimed cardinality and dominates each of the layers with zero, one and two left-part tokens, the…
- not_cop_win_two_of_dominating_cycleThe statement
cop_win_two_of_dominating_cycleis false: The theorem is FALSE. A concrete counterexample is the Petersen graph P on 10… - 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
Given a type V, a simple graph G on V, and a subset S of V, simple_graph_is_dominating G S is defined to hold if and only if for every vertex v : V, either v ∈ S or there exists some u ∈ S such that u is adjacent to v in G (G.Adj u v). (That is, S is a dominating set of G.)
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
/-- Predicate that a set of vertices is a dominating set in a simple graph. -/ def simple_graph_is_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop := ∀ v : V, v ∈ S ∨ ∃ u ∈ S, G.Adj u v