simple_graph_is_chain_graph
def
G is a chain graph with bipartition (A, V \ A): every edge joins A to its complement, and the neighbourhoods of the vertices of A are totally ordered by inclusion.
Statement
def simple_graph_is_chain_graph {V : Type*} (G : SimpleGraph V) (A : Set V) : Prop
- Defined in
- arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Sec. 6 (chain graphs: bipartite graphs whose neighbourhoods on one side are nested).
- Verified
- 14 Oct 2026
- Axioms
- none listed
- Used by 2
- simple_graph_is_chain_graph_complete_bipartiteThe complete bipartite graph K_{a,b} is a chain graph (all vertices on one side have the same neighbourhood).
- chain_graph_two_independence_number_eq_upper_two_star_forming_numberFor every finite chain graph G, the dissociation number β₂(G) equals the upper 2-star-forming number SF₂(G).
Lean source view module on GitHub
/-- A chain graph with bipartition `(A, Aᶜ)`: bipartite, with the neighbourhoods of the vertices of `A` nested. -/ def simple_graph_is_chain_graph {V : Type*} (G : SimpleGraph V) (A : Set V) : Prop := (∀ u v, G.Adj u v → (u ∈ A ↔ v ∉ A)) ∧ ∀ a₁ ∈ A, ∀ a₂ ∈ A, G.neighborSet a₁ ⊆ G.neighborSet a₂ ∨ G.neighborSet a₂ ⊆ G.neighborSet a₁