L(d,2,1)-Labeling of Simple Graphs
An L(3, 2, 1)-labeling is a simplified model for the channel assignment problem. It is a natural generalization of the widely studied L(2, 1)labeling. An L(3, 2, 1)-labeling of a graph G is a function f from the vertex set V (G) to the set of positive integers such that for any two vertices x, y, if d(x, y) = 1, then |f(x) − f(y)| ≥ 3; if d(x, y) = 2, then |f(x) − f(y)| ≥ 2; and if d(x, y) = 3, then |f(x) − f(y)| ≥ 1. The L(3, 2, 1)-labeling number k(G) of G is the smallest positive integer k such that G has an L(3, 2, 1)-labeling with k as the maximum label. In this paper we determine the L(3, 2, 1)-labeling number for paths, cycles, caterpillars, nary trees, complete graphs and complete bipartite graphs. We also present an upper bound for k(G) in terms of the maximum degree of G.
Distance-constrained labeling of complete trees
We study vertex labelings ? : V ? { 0 , 1 , 2 , ? } of a graph G = ( V , E ) which assign nonnegative integers to the vertices and the restrictions depend on the distances in G . Fixing a positive integer d , the requirement is that if vertices u and v are at distance i apart (where 1 ? i ? d ), then | ? ( u ) - ? ( v ) | d - i must hold. A corollary of the main result of this paper is an exact formula for the smallest possible value of ? max v ? V ? ( v ) ?for trees whose internal vertices all have the same degree and all leaves are at distance d / 2 from the central vertex (for d even) or at distance ( d - 1 ) / 2 from the central edge (for d odd). The case of even diameter extends the main theorem of Li et?al. (2010) on complete rooted trees with fixed down-degree and height.
New Spectrum Management Tools
This paper addresses the problem of devising reasonably accurate and widely applicable frequency allocation and assignment algorithms. The theoretical approach is summarized and the algorithms are described. The algorithms are automated via a FORTRAN program which incorporates the general frequencydistance assignment model. The program is structured to minimize the difficulty of replacing this model with models of other assignment problems. Applications to several important spectrum management problems are discussed.