simple_graph_local_avg_dominating_order
def
avd_v(G): the local average order of dominating sets containing v, i.e. the average size of the dominating sets of G that contain v.
Statement
def simple_graph_local_avg_dominating_order {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : ℚ
- Defined in
- arXiv:2610.11446 (On the local average order of dominating sets), Sec. 1 (avd_v(G) = Σ_{S ∈ D_v(G)} |S| / |D_v(G)|).
- Verified
- 09 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_dominating_sets_containingD_v(G): the dominating sets of G that contain v, where S dominates G when every vertex is in S or adjacent to a vertex of S.
- Used by 12
- 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_local_avg_dominating_order_bot_threeIn the edgeless graph on 3 vertices, the only dominating set is the whole vertex set, so avd_v = 3.
- simple_graph_local_avg_dominating_order_lt_of_four_leFor n ≥ 4 the upper bound (5n−1)/6 is never attained: if G has order n ≥ 4 and no isolated vertices, then avd_v(G) < (5n−1)/6 for every…
- simple_graph_local_avg_dominating_order_geFor every finite graph G of order n and every vertex v, the dominating sets containing v have average size at least (n+1)/2, with equality…
- 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…
- simple_graph_local_avg_dominating_order_eq_add_half_mul_of_leaf_neighborsIf every member of a finite set L of vertices is a leaf neighbour of v (G.Adj v ℓ and deg ℓ = 1 for ℓ ∈ L), then avd_v(G) = |L|/2 +…
- simple_graph_local_avg_dominating_order_complete_fourIn K₄, the dominating sets containing a fixed vertex have average size 5/2 = (4+1)/2.
- simple_graph_local_avg_dominating_order_eq_half_add_of_leaf_neighborLeaf recursion: if ℓ is a leaf neighbour of v (G.Adj v ℓ and deg ℓ = 1), then avd_v(G) = 1/2 + avd_v(G - ℓ), where G - ℓ is the subgraph…
- simple_graph_local_avg_dominating_order_of_degree_eq_card_sub_twoLet G be a connected graph of order n ≥ 3 and v a vertex of degree n − 2, with u the vertex other than v not adjacent to v. Then the…
- 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…
- simple_graph_local_avg_dominating_order_stem_le_of_card_le_two_mul_degreeIf G has no isolated vertices and |V| ≤ 2 deg(v), then avd_v(G) ≤ (4|V|+1)/6. This is the large-degree regime of the target's inequality,…
- simple_graph_local_avg_dominating_order_le_of_no_isolatedIf the finite graph G of order n has no isolated vertices, then for every vertex v the dominating sets containing v have average size at…
Lean source view module on GitHub
/-- `avd_v(G)`: the local average order of dominating sets containing `v`, the average size of the dominating sets of `G` that contain `v`. -/ def simple_graph_local_avg_dominating_order {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : ℚ := (∑ S ∈ simple_graph_dominating_sets_containing G v, (S.card : ℚ)) / (simple_graph_dominating_sets_containing G v).card