simple_graph_avg_dominating_order
def
avd(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 Beaton--Cameron, related to the local quantity avd_v(G) by the leaf recursion.
Statement
def simple_graph_avg_dominating_order {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℚ
- Source
- step towards simple_graph_local_avg_dominating_order_stem_le
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_dominating_setsD(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.
- Used by 7
- 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…
- 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…
- 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
/-- avd(G): the global average order of the dominating sets of G, the average size of *all* dominating sets (not just those through a fixed vertex). -/ def simple_graph_avg_dominating_order {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℚ := (∑ S ∈ simple_graph_dominating_sets G, (S.card : ℚ)) / (simple_graph_dominating_sets G).card