Labelings of graphs with fixed and variable edge-weights

BABILON, R; V JELINEK; Daniel KRÁĽ and P VALTR. Labelings of graphs with fixed and variable edge-weights. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2007, vol. 21, No 3, p. 688-706. ISSN 0895-4801. Available from: https://dx.doi.org/10.1137/040619545.

Basic information

Original name

Labelings of graphs with fixed and variable edge-weights

Authors

BABILON, R; V JELINEK; Daniel KRÁĽ and P VALTR

Edition

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

---

Other information

Language

English

Type of outcome

Article in a journal

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.674

DOI

http://dx.doi.org/10.1137/040619545

UT WoS

000251174200009

Keywords in English

channel assignment problem; graph labeling with distance conditions

---

Abstract

V originále

Motivated by L( p, q)-labelings of graphs, we introduce a notion of lambda-graphs: a lambda-graph G is a graph with two types of edges: 1-edges and x-edges. For a parameter x epsilon [0, 1], a proper labeling of G is a labeling of vertices of G by nonnegative reals such that the labels of the endvertices of a 1-edge differ by at least 1 and the labels of the endvertices of an x-edge differ by at least x; lambda(G)(x) is the smallest real such that G has a proper labeling by labels from the interval [0, lambda(G)(x)]. We study properties of the function lambda(G)(x) for finite and infinite lambda-graphs and establish the following results: if the function lambda(G)(x) is well defined, then it is a piecewise linear function of x with finitely many linear parts. Surprisingly, the set Lambda(alpha, beta)of all functions lambda(G) with lambda(G)(0) = alpha and lambda(G)(1) = beta is finite for any alpha <= beta. We also prove a tight upper bound on the number of segments for finite lambda-graphs G with convex functions lambda(G)(x).