Real Number Graph Labeling with Distance Conditions

The theory of integer λ-labellings of a graph, introduced by Griggs and Yeh, seeks to model efficient channel assignments for a network of transmitters. To prevent interference, labels for nearby vertices must be separated by specified amounts ki depending on the distance i, 1 ≤ i ≤ p. Here we expand the model to allow real number labels and separations. The main finding (“D-set Theorem”) is that for any graph, possibly infinite, with maximum degree at most ∆, there is a labelling of minimum span in which all of the labels have the form �p i=1 aiki, where the ai’s are integers ≥ 0. We show that the minimum span is a continuous function of the ki’s, and we conjecture that it is piecewise linear with finitely many pieces. Our stronger conjecture is that the coefficients ai can be bounded by a constant depending only on ∆ and p. We offer results in strong support of the conjectures, and we give formulas for the minimum spans of several graphs with general conditions at distance two. Keywords channel assignment, graph labelling, generalized coloring 1 Integer Labellings with Distance Conditions A steadily growing body of literature has evolved in the past 15 years on efficient integer labellings of the vertices of a finite simple graph with restrictions not only on adjacent vertices–as is the case with traditional graph coloring–but also on vertices at distance two