simple_graph_dominating_sets
def
D(G): the dominating sets of G, i.e. the finite vertex sets S such that every vertex of G lies in S or is adjacent to a vertex of S.
Statement
def simple_graph_dominating_sets {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Finset (Finset V)
- Source
- step towards simple_graph_local_avg_dominating_order_stem_le
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 9
- simple_graph_avg_dominating_order_complete_twoThe global average order of dominating sets of K2 is 4/3 (the three dominating sets {0}, {1}, {0,1} have sizes 1, 1, 2). Note this is…
- dominating_partition_functionThe dominating set partition function Z_G(lam) of a finite simple graph G is the sum over all dominating sets S of G of lam^{|S|}.
- simple_graph_avg_dominating_orderavd(G): the global average order of dominating sets of G, i.e. the average size of all dominating sets of G. This is the quantity of…
- dominating_occupancyThe normalized lambda-biased dominating occupancy rho_G(lam) of a finite simple graph G on vertex set V is the sum over all dominating…
- simple_graph_local_avg_dominating_order_eq_avg_of_isolatedIf v is an isolated vertex of G (deg v = 0), then avd_v(G) = avd(G): every dominating set contains v, so the dominating sets containing v…
- dominating_average_stability_path_five_meanThe five-vertex path has average dominating-set size55/17.
- 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.
- dominating_occupancy_one_eq_avg_dominating_order_div_cardAt activity lam = 1, the dominating occupancy equals the average dominating set order divided by the number of vertices.
- simple_graph_avg_dominating_order_deficit_bridgeThe dominating set order deficit 2n/3 - avd(G) can be rewritten as (2n|D(G)| - 3 ∑_{S∈D(G)} |S|) / (3|D(G)|).
Lean source view module on GitHub
/-- The family of all dominating sets of G; `simple_graph_dominating_sets_containing G v` is the subfamily of those containing v. -/ def simple_graph_dominating_sets {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Finset (Finset V) := Finset.univ.filter (fun S => ∀ w, w ∈ S ∨ ∃ u ∈ S, G.Adj u w)