simple_graph_is_k_star_forming
def
A vertex set S is k-star-forming when, for every vertex v outside S, the induced graph G[S ∪ {v}] contains a copy of the star K_{1,k} that contains v (v as the centre or as a leaf).
Statement
def simple_graph_is_k_star_forming {V : Type*} (G : SimpleGraph V) (k : ℕ) (S : Finset V) : Prop
- Defined in
- arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Definition 2.1.
- Verified
- 14 Oct 2026
- Axioms
- none listed
- Used by 9
- exists_triangle_free_k_independence_number_lt_upper_k_star_forming_numberThere is a triangle-free graph H on 10 vertices with β_4(H) = 7 < 8 = SF_4(H).
- simple_graph_k_independence_number_eq_card_of_degree_ltIf every vertex of the finite graph G has degree less than k, then β_k(G) = SF_k(G) = |V(G)|.
- simple_graph_k_independence_number_le_upper_k_star_forming_numberFor every finite graph G and every k, β_k(G) ≤ SF_k(G).
- simple_graph_is_k_star_forming_iffFor k ≥ 1, a vertex set S is k-star-forming if and only if every vertex v outside S has at least k neighbours in S, or has a neighbour u…
- simple_graph_is_k_star_forming_monoEvery superset of a k-star-forming set is k-star-forming.
- complete_bipartite_k_independence_number_eq_upper_k_star_forming_numberFor k ≥ 2 and a, b ≥ k, the complete bipartite graph K_{a,b} has β_k(K_{a,b}) = SF_k(K_{a,b}) = max{a, b, 2k − 2}.
- 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).
- simple_graph_is_minimal_k_star_formingA minimal k-star-forming set: a k-star-forming set no proper subset of which is k-star-forming.
- simple_graph_is_k_star_forming_univIn a finite graph the whole vertex set is k-star-forming, for every k (there is no vertex outside it).
Lean source view module on GitHub
/-- A vertex set `S` is `k`-star-forming when every `v ∉ S` lies in a copy of `K_{1,k}` in `G[S ∪ {v}]`. -/ def simple_graph_is_k_star_forming {V : Type*} (G : SimpleGraph V) (k : ℕ) (S : Finset V) : Prop := ∀ v, v ∉ S → ∃ c : V, ∃ L : Finset V, (c = v ∨ c ∈ S) ∧ (∀ x ∈ L, x = v ∨ x ∈ S) ∧ L.card = k ∧ (∀ x ∈ L, G.Adj c x) ∧ (v = c ∨ v ∈ L)