Informace o publikaci
The channel assignment problem with variable weights
| Autoři | |
|---|---|
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1137/040619636 |
| Klíčová slova | channel assignment problem; graph labeling with distance conditions |
| Popis | A lambda-graph G is a (finite or infinite) graph with k types of edges, x(1)-edges,..., x(k)-edges. A labeling c of the vertices of G by nonnegative reals is proper with respect to reals x(1),..., x(k) if the labels of the end-vertices of an x(i)-edge differ by at least x(i). The span of the labeling c is the supremum of the labels used by c. The lambda-function lambda(G)(x(1),..., x(k)) is the infimum of the spans of all the proper labelings with respect to x(1),..., x(k). We show that the lambda-function of any graph G is piecewise linear in x(1),..., x(k) with finitely many linear parts (unless the lambda-function is infinite). Moreover, we show that for all integers k and chi, there exist constants C-k,C-chi and D-k,D-chi such that the lambda-function of every lambda-graph G with k types of edges and chromatic number at most. is comprised of at most Ck,. linear parts, and that the coefficients of x(1),..., x(k) of the linear functions comprising lambda(G)(x(1),..., x(k)) are integers between 0 and D-k,D-chi. Among others, our results yield proofs of the piecewise linearity conjecture, coefficient bound conjecture, and delta bound conjecture of Griggs and Jin [SIAM J. Discrete Math., 20 (2006), pp. 302-327]. |