simple_graph_vertex_dominated
def
A vertex $v$ of a simple graph $H$ is dominated if there exists a vertex $t \neq v$ in $H$ such that the closed neighbourhood of $v$ is contained in the closed neighbourhood of $t$, that is, $N_H[v] \subseteq N_H[t]$.
Statement
def simple_graph_vertex_dominated {V : Type*} (H : SimpleGraph V) (v : V) : Prop
- Defined in
- arXiv:2611.14430 Section 2
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Used by 2
- not_simple_graph_vertex_dominated_of_isolatedAn isolated vertex in a simple graph $H$ (a vertex with empty open neighbourhood) is not dominated by any vertex.
- simple_graph_vertex_dominated_complete_twoIn the complete graph on two vertices, vertex 0 is dominated.
Read back from the Lean
For an arbitrary type V, a simple graph H on V, and a vertex v : V, simple_graph_vertex_dominated H v is defined to hold if and only if there exists a vertex t : V such that t ≠ v and the closed neighborhood of v is a subset of the closed neighborhood of t (that is, {v} ∪ H.neighborSet v ⊆ {t} ∪ H.neighborSet t).
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 v is dominated by another vertex in H if its closed neighbourhood is contained in that of the other vertex. -/ def simple_graph_vertex_dominated {V : Type*} (H : SimpleGraph V) (v : V) : Prop := ∃ t : V, t ≠ v ∧ insert v (H.neighborSet v) ⊆ insert t (H.neighborSet t)