Distance Four Graph Labelings for the Channel Assignment Problem

摘要

Let d(u, v) be the distance between the vertices u and v in a graph G. An L(4,3,2,1)-labeling of G is a function f: V(G)→ {0, 1,...} such that for every u,v ∈V(G), |f(u)-f(v)| ≥5-d(u,v) if 1 ≦ d(u, v) ≦ 4. The span of f is the difference between the largest and the smallest numbers in f(V(G)). The λ_(4,3,2,1)-number of G is the minimum span over all L(4,3,2,1)-labelings of G. The L(4,3,2,1)-labeling problem is to find the λ_(4,3,2,1)-number of G and it can model the channel assignment problem which asks for assigning channel frequencies to transmitters in a broadcasting network with the aim of avoiding undesired interference between nodes with distance at most four. In this paper, we study the L(4,3,2,1)-labelings of paths, cycles, and prisms, and some of their optimal λ_(4,3,2,1)-labelings are given.