Labelings of Graphs with Fixed and Variable Edge-Weights
Robert Babilon, Vít Jelínek, Daniel Král͏̌, Pável Valtr · SIAM Journal on Discrete Mathematics · 2007
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\in[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\le\beta$. We also prove a tight upper bound on the number of segments for finite $\lambda$-graphs G with convex functions $\lambda_G(x)$.