Real Number Graph Labellings with Distance Conditions
Jerrold R. Griggs, Xiaohua Teresa Jin · SIAM Journal on Discrete Mathematics · 2006
The theory of integer $\lambda$-labellings of a graph, introduced by Griggs and Yeh [J. R. Griggs and R. K.-C. Yeh, SIAM J. Discrete Math., 5 (1992), pp. 586-595], seeks to model efficient channel assignments for a network of transmitters. To prevent interference, labels for nearby vertices must be separated by specified amounts $k_i$ depending on the distance i, $1\le i\le 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 $\Delta$, there is a labelling of minimum span in which all of the labels have the form $\sum_{i=1}^p a_i k_i$, where the $a_i$'s are integers $\ge0$. We show that the minimum span is a continuous function of the $k_i$'s, and we conjecture that it is piecewise linear with finitely many pieces. Our stronger conjecture is that the coefficients $a_i$ can be bounded by a constant depending only on $\Delta$ 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.