AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it