simple_graph_dominating_sets_containing
def
D_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.
Statement
def simple_graph_dominating_sets_containing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : Finset (Finset V)
- Defined in
- arXiv:2610.11446 (On the local average order of dominating sets), Sec. 1 (dominating sets; D_v(G)).
- Verified
- 09 Oct 2026
- Axioms
- none listed
- Used by 11
- 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_orderavd_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.
- 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
/-- `𝒟_v(G)`: the dominating sets of `G` that contain the vertex `v` (a set `S` dominates `G` when every vertex is in `S` or adjacent to a vertex of `S`). -/ def simple_graph_dominating_sets_containing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : Finset (Finset V) := Finset.univ.filter (fun S => v ∈ S ∧ ∀ w, w ∈ S ∨ ∃ u ∈ S, G.Adj u w)