Alladi Ramakrishnan Hall

Distance labellings of graphs

Sanming Zhou

The University of Melbourne, Australia

Let $h_1 \ge h_2 \ge \cdots \ge h_d$ be nonnegative integers. An
$L(h_1, h_2, \ldots, h_d)$-labelling of a (finite or infinite) graph $G$ is an assignment $\phi$ of nonnegative integers (labels) to its vertices such that for $i = 1, 2, \ldots, d$ and $u, v \in V(G)$, if $d(u, v) = i$, then $|\phi(u) - \phi(v)| \ge h_i$. The span of such a labelling is the difference between the maximum and minimum labels used. The minimum span over all $L(h_1, h_2, \ldots, h_d)$-labellings of $G$ is called the $\lambda_{h_1, h_2, \ldots, h_d}$-number of $G$. Motivated by applications in frequency assignment, the problem of determining this invariant together with optimal labellings has received considerable attention over the past more than one decade, especially in the case when $d=2$ or $3$.

In this talk, I will review recent progress on this problem for $d=2$ or $3$. Among other things I will discuss recent results on the $\l_{2,1}$-number of
outerplanar graphs and the $\l_{h,1,1}$-number of trees.