图的距离标号与L(2,1)-标号

1. 基本定义与背景
   图的距离标号是一种顶点标号方式，要求任意两个顶点根据其距离分配不同的标号值。具体地，设图 \(G = (V, E)\)，一个标号函数 \(f: V \to \{0,1,2,\dots\}\) 需满足：若两个顶点 \(u\) 和 \(v\) 的距离为 \(d(u,v)\)，则 \(|f(u) - f(v)| \geq k - d(u,v) + 1\)，其中 \(k\) 为标号跨度参数。
   L(2,1)-标号 是距离标号的特例，要求：

   • 相邻顶点标号差至少为 2；
   • 距离为 2 的顶点标号差至少为 1。
     目标是最小化最大标号值，称为 L(2,1)-标号数，记为 \(\lambda(G)\)。

2. 标号约束的直观解释

   • 相邻顶点差≥2：避免相邻顶点标号接近，模拟无线网络中相邻信道需较大间隔以减少干扰。
   • 距离2顶点差≥1：确保公共邻居的顶点标号不同，进一步降低干扰。
     例如，路径图 \(P_3\) 的顶点序列标号可为 (2, 0, 2)，满足相邻差为2，距离2的顶点差为0（允许相同，因距离2无差≥1的要求需再检验：顶点1与3距离2，标号差0，不满足差≥1？需修正为 (3,0,2) 或 (2,0,3)）。

3. 标号数的计算方法

   • 对任意图 \(G\)，有 \(\lambda(G) \geq \Delta + 1\)，其中 \(\Delta\) 为最大度。
   • 常见图的标号数：

• 路径图 \(P_n\)：\(\lambda(P_n) = 4\)（当 \(n \geq 4\)）。
• 圈图 \(C_n\)：\(\lambda(C_n) = 4\)（若 \(n \not\equiv 0 \pmod{3}\)），否则需调整。
• 树：\(\lambda(T) \leq \Delta + 2\)。
  • 通用界：Griggs-Yeh猜想（已证明）指出 \(\lambda(G) \leq \Delta^2\)。

4. 算法与复杂性

   • 确定 \(\lambda(G)\) 是 NP-hard 问题，即使对平面图或最大度4的图。
   • 近似算法：贪心策略或基于广度优先搜索（BFS）的标号可达 \(\lambda(G) \leq \Delta^2 + \Delta\)。
   • 精确算法：对树或二部图可用动态规划在多项式时间求解。

5. 应用与扩展

   • 无线网络信道分配：顶点代表基站，边代表干扰，标号对应信道频率。
   • L(p,q)-标号：推广到任意距离约束，要求距离 \(d\) 的顶点标号差 ≥ \(p - q \cdot d\)（需调整公式）。
   • 无圈标号：标号函数为单射，且每个标号类诱导子图为无圈，是L(2,1)-标号的变体。