is_ve_dominating
def
A subset S of vertices in a simple graph G is a vertex-edge dominating set if for all vertices x and y with G.Adj x y, there exists u in S such that u = x, or G.Adj u x, or u = y, or G.Adj u y.
Statement
def is_ve_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
- Defined in
- arXiv:2610.26912 Section 1
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Used by 3
- not_is_fix_v0_of_isolatedAn isolated vertex v in a finite simple graph G (with empty neighborhood) does not belong to V_fix^0(G).
- is_fix_v0A vertex v of a finite simple graph G belongs to V_fix^0(G) if v is in V^0(G) and v belongs to every minimum vertex-edge dominating set S…
- gamma_veThe vertex-edge domination number gamma_ve(G) of a finite simple graph G is the minimum cardinality of a finite subset S of V that is a…
Read back from the Lean
Given a type V, a simple graph G on V, and a subset S of V, is_ve_dominating G S asserts that for every pair of vertices x, y : V, if x and y are adjacent in G, then there exists some vertex u ∈ S such that u = x, u is adjacent to x in G, u = y, or u is adjacent to y in 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
/-- A vertex set S is a vertex-edge dominating set if every edge has an endpoint in the closed neighborhood of some vertex in S. -/ def is_ve_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop := ∀ ⦃x y : V⦄, G.Adj x y → ∃ u ∈ S, u = x ∨ G.Adj u x ∨ u = y ∨ G.Adj u y