Labelling Cayley Graphs on Abelian Groups
Sanming Zhou · SIAM Journal on Discrete Mathematics · 2005
For given integers $j \ge k \ge 1$, an $L(j,k)$-labelling of a graph $\Ga$ is an assignment of labels---nonnegative integers---to the vertices of $\Ga$ such that adjacent vertices receive labels that differ by at least j, and vertices distance two apart receive labels that differ by at least k. The span of such a labelling is the difference between the largest and the smallest labels used, and the minimum span over all $L(j,k)$-labellings of $\Ga$ is denoted by $\l_{j,k}(\Ga)$. The minimum number of labels needed in an $L(j,k)$-labelling of $\Ga$ is independent of j and k, and is denoted by $\mu(\Ga)$. In this paper we introduce a general approach to $L(j,k)$-labelling Cayley graphs $\Ga$ over Abelian groups and deriving upper bounds for $\l_{j,k}(\Ga)$ and $\mu(\Ga)$. Using this approach we obtain upper bounds on $\l_{j,k}(\Ga)$ and $\mu(\Ga)$ for graphs $\Ga$ admitting a vertex-transitive Abelian group of automorphisms. Hypercubes $Q_d$ are examples of such graphs, and as consequences we obtain upper bounds for $\l_{j,k}(Q_d)$ and $\mu(Q_d)$. We also obtain the exact values of $\l_{j,k}(\Ga)$ ($2k \ge j \ge k$) and $\mu(\Ga)$ for some Hamming graphs $\Ga$. The result shows that, under certain arithmetic conditions, these two invariants rely only on k and the orders of the two largest complete graph factors of the Hamming graph.