simple_graph_is_perfect_dominating
def
A subset D of vertices in a simple graph G is a perfect dominating set if every vertex v of G is dominated by exactly one vertex in D, that is, there exists a unique u in D such that u is adjacent to v or u equals v.
Statement
def simple_graph_is_perfect_dominating {V : Type*} (G : SimpleGraph V) (D : Set V) : Prop
- Defined in
- arXiv:2611.11191, Section 2
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Used by 1
- simple_graph_is_perfect_dominating_fin1In the edgeless graph on one vertex, the singleton vertex set is a perfect dominating set.
Read back from the Lean
Given a simple graph $G$ on a vertex type $V$ and a subset of vertices $D \subseteq V$, the definition asserts that for every vertex $v \in V$, there exists a unique vertex $u \in V$ such that $u \in D$ and either $v$ is adjacent to $u$ in $G$ or $v = u$. That is, every vertex in $V$ has exactly one neighbor (in the closed neighborhood sense) in $D$.
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 subset D of vertices in a simple graph G is a perfect dominating set if every vertex is dominated by a unique element of D. -/ def simple_graph_is_perfect_dominating {V : Type*} (G : SimpleGraph V) (D : Set V) : Prop := ∀ v : V, ∃! u ∈ D, G.Adj v u ∨ v = u