simple_graph_star_like_deletion_number
deforiginal
The star-like deletion number d_*(G) of a finite simple graph G is the minimum cardinality of a subset X of vertices such that the induced subgraph G - X is star-like.
Statement
noncomputable def simple_graph_star_like_deletion_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ
- Related work
- arXiv:2208.10475v2: The average size of a dominating set in a graph
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_is_star_likeG is star-like: every vertex is either a leaf (degree one) or an l-stem with 1 ≤ l ≤ 2.
- Used by 5
- simple_graph_star_like_deletion_number_le_cardFor every finite simple graph G, deleting all vertices leaves the empty graph, which is star-like, so the star-like deletion number d_*(G)…
- dominating_average_stability_constant_lower_boundAny multiplicative stability coefficient valid on the five-vertex path is at least51/5. This is a necessary constant, not the universal…
- dominating_average_stability_path_five_deletionThe minimum star-like vertex deletion distance of the five-vertex path is exactly1.
- dominating_average_star_like_vertex_stability_of_card_twoFor every finite simple graph G on 2 vertices with no isolated vertex, the stability inequality 5 d_*(G) ≤ 51 (2·2/3 - avd(G)) holds.
- simple_graph_star_like_deletion_number_eq_zero_of_star_likeIf a finite simple graph G is star-like, its star-like deletion number d_*(G) is zero.
Read back from the Lean
Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, simple_graph_star_like_deletion_number G is defined as the infimum (in ℕ) of the set of all natural numbers k for which there exists a finset X : Finset V of cardinality k such that the induced subgraph of G on the complement Xᶜ is "star-like" (simple_graph_is_star_like).
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
/-- The minimum number of vertices whose deletion from G leaves an induced star-like subgraph. -/ noncomputable def simple_graph_star_like_deletion_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ := open scoped Classical in sInf {k : ℕ | ∃ X : Finset V, simple_graph_is_star_like (G.induce (Xᶜ : Set V)) ∧ X.card = k}