Informace o publikaci
Labelings of graphs with fixed and variable edge-weights
| Autoři | |
|---|---|
| Rok publikování | 2007 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1137/040619545 |
| Klíčová slova | channel assignment problem; graph labeling with distance conditions |
| Popis | 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). |