Radio labelings of distance graphs
Résumé
Motivated by the Channel Assignment Problem, we study radio k-labelings of graphs. A radio k-labeling of a connected graph G is an assignment c of non-negative integers to the vertices of G such that |c(x)−c(y)|≥k+1−d(x,y), for any two vertices x and y, x≠y, where d(x,y) is the distance between x and y in G. In this paper, we study radio k-labelings of distance graphs, i.e., graphs with the set Z of integers as vertex set and in which two distinct vertices i,j∈Z are adjacent if and only if |i−j|∈D. We give some lower and upper bounds for radio k-labelings of distance graphs with distance sets D(1,2,...,t), D(1,t) and D(t−1,t) for any positive integer t>1.