simple_graph_power
def
The d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of length at most d in G.
Statement
def simple_graph_power {V : Type*} (G : SimpleGraph V) (d : ℕ) : SimpleGraph V
- Defined in
- arXiv:2610.09300 (On graphs whose powers are well-covered), Sec. 1 and Sec. 2 (the d-th power G^d); the distance is Mathlib's extended distance edist, so vertices in different components are never adjacent.
- Verified
- 11 Oct 2026
- Axioms
- none listed
- Used by 28
- star_graph_power_two_eq_topFor any natural number m, the square of the star graph on m + 1 vertices is the complete graph.
- simple_graph_power_well_covered_not_ball_union_subsetLet G be a finite graph and d ≥ 1 with G^d well-covered. Then there are no vertices s, t, w with d_G(s, t) ≥ d + 1 and B_d(s) ∪ B_d(t) ⊆…
- complete_bipartite_two_two_all_powers_well_coveredFor every positive integer d, the d-th power of the complete bipartite graph K_{2,2} is well-covered.
- bipartite_ravindra_matching_power_two_well_covered_diam_le_twoIf a finite connected bipartite simple graph G admits a perfect matching M with complete bipartite neighborhoods and its second power G^2…
- diam_le_one_of_forall_power_well_covered_of_degree_eq_oneIf a finite connected graph G has a vertex of degree 1 and G^d is well-covered for every d ≥ 1, then diam(G) ≤ 1 (G is K_2). In particular…
- forall_power_well_covered_of_well_covered_diam_le_twoLet G be a finite connected well-covered graph of diameter at most 2. Then G^d is well-covered for every d ≥ 1.
- cycle_seven_power_one_well_coveredThe first power (the graph itself) of the 7-cycle graph is well-covered.
- exists_planar_all_powers_well_covered_diam_eq_threeThere exists a finite connected simple planar graph G with at least two vertices whose diameter is exactly 3 and such that every positive…
- cycle_five_all_powers_well_coveredFor every positive integer d, the d-th power of the 5-cycle graph C_5 is well-covered.
- 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…
- cycle_seven_all_powers_well_coveredFor every positive integer d, the d-th power of the 7-cycle graph C_7 is well-covered.
- spectral_extremal_chromatic_numberFor an integer k ≥ 1 and real number r, the extremal distance-k chromatic number under spectral radius constraint r, denoted χ_λ(k, r), is…
- 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…
- forall_power_well_covered_of_well_covered_diam_le_threeLet G be a finite connected simple graph of diameter at most 3. If G and its second power G^2 are both well-covered, then every positive…
- cycle_seven_power_ge_three_well_coveredEvery power d ≥ 3 of the 7-cycle graph is well-covered: since diam(C_7) = 3 ≤ d, the d-th power is the complete graph K_7 and every…
- exists_connected_all_powers_well_covered_diam_geFor every positive integer D, there exists a finite connected simple graph G with diameter at least D such that every positive power G^d…
- bipartite_all_powers_well_covered_diameter_le_twoEvery finite connected bipartite simple graph G with at least two vertices whose positive integer powers G^d (for d ≥ 1) are all…
- simple_graph_eccent_eq_diam_of_power_well_coveredLet G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then every vertex of G has eccentricity D (G is…
- simple_graph_no_leaf_of_power_well_coveredLet G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then G has no leaves (no vertex of degree 1).
- spectral_extremal_clique_numFor an integer k ≥ 1 and real number r, the extremal distance-k clique number under spectral radius constraint r, denoted ω_λ(k, r), is…
- exists_triangle_free_all_powers_well_covered_diam_eq_threeThere exists a finite connected triangle-free simple graph G with at least two vertices whose diameter is exactly 3 and such that every…
- simple_graph_has_well_covered_powersA finite simple graph G has the well-covered powers property if for every integer d ≥ 1, the d-th graph power G^d is well-covered.
- cycle_seven_power_two_well_coveredThe square of the 7-cycle graph is well-covered: all maximal independent sets have size 2.
- boxProd_completeGraph_all_powers_well_coveredLet G be a finite connected nontrivial graph, and let t be an integer with t > |V(G)|. If every positive power G^d (d ≥ 1) is…
- complete_graph_two_all_powers_well_coveredThe complete graph on 2 vertices K_2 is connected, has diameter 1, and every positive power K_2^d (d ≥ 1) is well-covered.
- simple_graph_power_oneG^1 = G.
- spectral_extremal_clique_num_le_chromatic_numberFor every natural number k and real number r, the extremal distance-k clique number spectral_extremal_clique_num k r is less than or equal…
Lean source view module on GitHub
/-- The `d`-th power of a graph: distinct vertices are adjacent when joined by a walk of length at most `d`. -/ def simple_graph_power {V : Type*} (G : SimpleGraph V) (d : ℕ) : SimpleGraph V where Adj u v := u ≠ v ∧ G.edist u v ≤ d symm := ⟨fun u v (h : u ≠ v ∧ G.edist u v ≤ d) => ⟨h.1.symm, by rw [SimpleGraph.edist_comm]; exact h.2⟩⟩ loopless := ⟨fun u h => h.1 rfl⟩