Publication details

Labelings of graphs with fixed and variable edge-weights

Authors

BABILON R JELINEK V KRÁĽ Daniel VALTR P

Year of publication 2007
Type Article in Periodical
Magazine / Source SIAM Journal on Discrete Mathematics
Citation
Doi http://dx.doi.org/10.1137/040619545
Keywords channel assignment problem; graph labeling with distance conditions
Description 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).

You are running an old browser version. We recommend updating your browser to its latest version.

More info