AFTD Auto-Formalizing Theoretical Domains

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

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|
See it in the graphDiscuss this resultChallenge it