digraph_is_quasi_kernel
def
A subset Q of vertices in a digraph D is a quasi-kernel if Q is independent (no arcs between distinct vertices of Q) and 2-dominating (every vertex v is either in Q, an out-neighbor of Q, or an out-neighbor of an out-neighbor of Q).
Statement
def digraph_is_quasi_kernel {α : Type*} (D : Digraph α) (Q : Finset α) : Prop
- Source
- step towards digraph_small_quasi_kernel_exists
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 2
- digraph_not_is_quasi_kernel_empty_of_nonemptyThe empty set is not a quasi-kernel in any nonempty digraph.
- digraph_is_quasi_kernel_empty_of_isEmptyIn an empty digraph, the empty set is a quasi-kernel.
Lean source view module on GitHub
/-- A subset Q of vertices in a digraph is a quasi-kernel if it is independent and every vertex of the digraph is in Q or reachable from Q by a directed path of length 1 or 2. -/ def digraph_is_quasi_kernel {α : Type*} (D : Digraph α) (Q : Finset α) : Prop := (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧ (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)