Distance-constrained labellings of Cartesian products of graphs

Abstract

An $L(h_1,h_2,\dots ,h_l)$-labelling of a graph $G$ is a mapping $\varphi :V(G)\to \{0,1,2,\dots \}$ such that for $1\le i\le l$ and each pair of vertices $u,v$ of $G$ at distance $i$, we have $|\varphi (u)-\varphi (v)|\ge h_i$. The span of $\varphi$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $\varphi$, and ${\lambda }_{h_1,h_2,\dots ,h_l}(G)$ is defined as the minimum span over all $L(h_1,h_2,\dots ,h_l)$-labellings of $G$. In this paper we study ${\lambda }_{h,1,\dots ,1}$ for Cartesian products of graphs, where $(h,1,\dots ,1)$ is an $l$-tuple with $l\ge 3$. We prove that, under certain natural conditions, the value of this and three related invariants on a graph $H$ which is the Cartesian product of $l$ graphs attain a common lower bound. In particular, the chromatic number of the $l$-th power of $H$ equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of $H$ which contain a certain subgraph of $H$. All these results apply in particular to the class of Hamming graphs: if $q_1\ge \cdots \ge q_d\ge 2$ and $3\le l\le d$ then the Hamming graph $H=H_{q_1,q_2,\dots ,q_d}$ satisfies ${\lambda }_{q_l,1,\dots ,1}(H)=q_1{q}_2\dots q_l-1$ whenever $q_1{q}_2\dots q_{l-1}>3(q_{l-1}+1)q_l\dots q_d$. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.

Final version published in Discrete Applied Mathematics