关于图的L(2,1)-标号问题

On the Labeling L(2, 1) of Graph

图的L(2,1)-标号问题来自频率分配问题并且是NP-完全性问题.得到:(ⅰ)G是p个顶点的简单图,对正整数k≥3,当p≥2k2和Δ≥p/k时,有L(G)≤Δ2.(ⅱ)Δ(G)表示图G的最大度,则L(G)≥Δ(G)+1.Vi及Vi∩Vj= ,i≠j,则L(G)≤p+k-2.(ⅲ)若V(G)可划分为独立集V1,V2,…,Vk,且V(G)

The L(2, 1)-labeling problem of a graph G is from a variation of the channel assignment problem. In this paper, we have proved: (ⅰ) Let G be a simple graph with p vertices, for integer k≥3, and p≥2k^2 and Δ≥p/k, then L(G)≤Δ~2. (ⅱ) L(G)≥Δ(G)+1. (ⅲ) If V(G) can be divided into some independent sets V_1, V_2, …, V_k,that V(G)=∪ki=1 and V_i∩V_j=,i≠j ,then L(G)≤p+k-2.