simple_graph_is_star_like
def
G is star-like: every vertex is either a leaf (degree one) or an l-stem with 1 ≤ l ≤ 2.
Statement
def simple_graph_is_star_like {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Prop
- Defined in
- arXiv:2610.11446 (On the local average order of dominating sets), Lemma 5.1 (star-like graphs: every vertex is a leaf or an l-stem with l ≤ 2).
- Verified
- 09 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_leaf_neighbor_countThe number of leaf neighbours (neighbours of degree one) of a vertex v; v is an l-stem when this number is l ≥ 1.
- Used by 11
- 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)…
- simple_graph_star_like_deletion_numberThe 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…
- simple_graph_local_avg_dominating_order_eq_four_mul_add_one_of_universalRigidity in the universal-vertex regime: if G has no isolated vertices, v is adjacent to every other vertex (deg v = n − 1), and avd_v(G)…
- simple_graph_is_star_like_complete_twoK₂ is star-like.
- simple_graph_local_avg_dominating_order_stem_le_of_card_twoThe target statement at order n = 2: if |V| = 2 and G has no isolated vertices, then for every vertex v, avd_v(G) = (4·2+1)/6, v has…
- dominating_average_stability_path_five_deletionThe minimum star-like vertex deletion distance of the five-vertex path is exactly1.
- dominating_average_stability_path_five_delete_endpointDeleting an endpoint from the five-vertex path leaves a star-like induced graph.
- dominating_average_stability_path_five_not_starThe five-vertex path is not star-like.
- 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.
- not_simple_graph_is_star_like_complete_threeK₃ is not star-like (no vertex is a leaf or has a leaf neighbour).
- 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.
Lean source view module on GitHub
/-- `G` is star-like: every vertex is a leaf (degree one) or an `l`-stem with `1 ≤ l ≤ 2`. -/ def simple_graph_is_star_like {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Prop := ∀ w, G.degree w = 1 ∨ (1 ≤ simple_graph_leaf_neighbor_count G w ∧ simple_graph_leaf_neighbor_count G w ≤ 2)