J 2006

The channel assignment problem with variable weights

KRÁĽ, Daniel

Základní údaje

Originální název

The channel assignment problem with variable weights

Autoři

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2006, 0895-4801

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.518

Označené pro přenos do RIV

Ne

DOI

UT WoS

Klíčová slova anglicky

channel assignment problem; graph labeling with distance conditions
Změněno: 6. 11. 2020 10:57, Mgr. Darina Boukalová

Anotace

V originále

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].