simple_graph_clique_blowup
def
The clique blow-up H = G[K_{a_1}, …, K_{a_n}]: each vertex v_i of G is replaced by a clique Q_i on a_i vertices, and distinct vertices x ∈ Q_i, y ∈ Q_j are adjacent iff i = j or v_i v_j ∈ E(G).
Statement
def simple_graph_clique_blowup {V : Type*} (G : SimpleGraph V) (a : V → ℕ) : SimpleGraph (Σ i, Fin (a i))
- Defined in
- arXiv:2610.09300 (On graphs whose powers are well-covered), Sec. 1 and proof of Theorem 1.6 (clique blow-up, graph composition with cliques). Vertices are pairs ⟨i, x⟩ with x : Fin (a i).
- Verified
- 11 Oct 2026
- Axioms
- none listed
- Used by 5
- forall_power_well_covered_iff_clique_blowupLet G be a finite simple graph and a_1, …, a_n positive integers, H = G[K_{a_1}, …, K_{a_n}] its clique blow-up. Then G^d is well-covered…
- simple_graph_power_well_covered_iff_clique_blowupFor every d ≥ 1 and positive integers a_i, G^d is well-covered iff H^d is well-covered, where H = G[K_{a_1}, …, K_{a_n}].
- not_planar_all_powers_well_covered_characterizationIt is not the case that every finite connected simple planar graph G with at least two vertices whose powers G^d are all well-covered is…
- simple_graph_clique_blowup_coloring_frozen_iffFor a clique blowup G(w) with positive weights, a proper colouring α of G(w) is frozen iff for every colour i the set I_i(α) of vertices v…
- simple_graph_clique_blowup_edistIn the clique blow-up H of G, two vertices x ∈ Q_i and y ∈ Q_j with i ≠ j are at the same distance in H as v_i and v_j in G (including…
Lean source view module on GitHub
/-- The clique blow-up `G[K_{a_1}, …, K_{a_n}]`: each vertex `i` is replaced by a clique on `a i` vertices, and vertices in different cliques are adjacent when their parts are. -/ def simple_graph_clique_blowup {V : Type*} (G : SimpleGraph V) (a : V → ℕ) : SimpleGraph (Σ i, Fin (a i)) where Adj p q := (p.1 = q.1 ∧ p ≠ q) ∨ G.Adj p.1 q.1 symm := ⟨fun (p q : Σ i, Fin (a i)) (h : (p.1 = q.1 ∧ p ≠ q) ∨ G.Adj p.1 q.1) => by rcases h with ⟨h1, h2⟩ | h · exact Or.inl ⟨h1.symm, h2.symm⟩ · exact Or.inr h.symm⟩ loopless := ⟨fun (p : Σ i, Fin (a i)) (h : (p.1 = p.1 ∧ p ≠ p) ∨ G.Adj p.1 p.1) => by rcases h with ⟨-, h⟩ | h · exact h rfl · exact G.loopless.irrefl _ h⟩