Publication details
Labelings of graphs with fixed and variable edge-weights
| Authors | |
|---|---|
| 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). |