simple_graph_is_multi_radio_labeling
def
An (m,k)-radio labeling of G: each vertex gets a set of m nonnegative integer labels, and for any (possibly equal) vertices x, y and labels a of x, b of y with (x, a) ≠ (y, b), |a - b| >= k + 1 - d(x, y).
Statement
def simple_graph_is_multi_radio_labeling {V : Type*} (G : SimpleGraph V) (m k : ℕ) (f : V → Finset ℕ) : Prop
- Defined in
- arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Sec. 1 (definition of (m,k)-radio labelings)
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 13
- simple_graph_path_radio_labeling_four_mul_add_threeFor m >= 1, the labeling of the path P_{4m+3} that gives an odd vertex v the labels v, v+4, ..., v+4(m-1) and an even vertex v the labels…
- simple_graph_multi_radio_number_path_three_of_le_of_forallReduction of the thread goal to one finite statement per m: if no (m,3)-radio labeling of P_{4m+4} has all labels at most 8m - 2, then the…
- exists_radio_labeling_top_span_eqUpper bound: the labeling f(v_i) = {ik, (n+i)k, ..., ((m-1)n+i)k} is an (m,k)-radio labeling of K_n of span k(mn - 1).
- simple_graph_multi_radio_numberThe (m,k)-radio number lambda_k^m(G): the least span of an (m,k)-radio labeling of G.
- simple_graph_multi_radio_number_path_three_one_of_leFor every n >= 8 the (1,3)-radio number of the path P_n is exactly 7: the case m = 1 of the thread's goal (8m - 1 for n >= 4m + 4).
- exists_multi_radio_labeling_pathFor all n, m, k there is an (m,k)-radio labeling of the path P_n: on vertex v put the m labels (k+1)*(m*v + a) for a < m.
- simple_graph_path_radio_three_seven_extremal_uniqueThe case m = 1: the only (1,3)-radio labelings of P_7 with labels in [0, 6] are 4,1,6,3,0,5,2 and its mirror image.
- simple_graph_multi_radio_number_path_three_ltThe threshold 4m + 4 is sharp: the (m,3)-radio number of P_{4m+3} is less than 8m - 1.
- simple_graph_multi_radio_number_topFor n >= 2, k >= 1 and m >= 1, the (m,k)-radio number of the complete graph K_n is k(mn - 1).
- multi_label_span_ge_of_radio_labeling_topLower bound: every (m,k)-radio labeling of the complete graph K_n has span at least k(mn - 1).
- simple_graph_multi_radio_number_path_le_eight_mulFor n, m >= 1 the (m,3)-radio number of the path P_n is at most 8m - 1.
- simple_graph_multi_radio_number_path_monoThe (m,k)-radio number of the path P_n is nondecreasing in n: a labeling of P_{n+1} restricts to one of P_n.
- path_three_radio_labeling_span_ge_sevenFor n >= 8, every (1,3)-radio labeling of the path P_n has span at least 7; combined with the upper bound 8m-1 at m = 1 this gives that…
Lean source view module on GitHub
/-- An (m,k)-radio labeling of G: each vertex gets a set of m nonnegative integer labels, and for any (possibly equal) vertices x, y and labels a of x, b of y with (x, a) ≠ (y, b), |a - b| >= k + 1 - d(x, y). -/ def simple_graph_is_multi_radio_labeling {V : Type*} (G : SimpleGraph V) (m k : ℕ) (f : V → Finset ℕ) : Prop := (∀ v, (f v).card = m) ∧ ∀ x y, ∀ a ∈ f x, ∀ b ∈ f y, (x, a) ≠ (y, b) → (k + 1 : ℤ) - G.dist x y ≤ |(a : ℤ) - b|