Distance-constrained labellings of Cartesian products of graphs

Anna Lladó, Hamid Mokhtar, Oriol Serra, Sanming Zhou

Published 2020-06-17Version 1

An $L(h_1, h_2, \ldots, h_l)$-labelling of a graph $G$ is a mapping $\phi: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that for $1\le i\le l$ and each pair of vertices $u, v$ of $G$ at distance $i$, we have $|\phi(u) - \phi(v)| \geq h_i$. The span of $\phi$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $\phi$, and $\lambda_{h_1, h_2, \ldots, h_l}(G)$ is defined as the minimum span over all $L(h_1, h_2, \ldots, h_l)$-labellings of $G$. In this paper we study $\lambda_{h, 1, \ldots, 1}$ for Cartesian products of graphs. We prove that, if $G_1, \ldots, G_{l-1}$ and $G$ are non-trivial graphs with orders $q_1, \ldots, q_{l-1}$ and $q$, respectively, such that $q_1 q_2 \ldots q_{l-1} > 3(\min\{q_1, \ldots, q_{l-1}\}+1)q$ and $H = G_1 \Box \cdots \Box G_{l-1} \Box G$ contains a subgraph $K$ with order $q_1 q_2 \ldots q_{l}$ and diameter at most $l\ge 2$ then, for every integer $1 \le h \le q_{l}\le q$, $\lambda_{h, 1, \ldots, 1}(H)$ as well as three related invariants for $H$ all take the value $q_1 q_2 \ldots q_{l} - 1$. In particular the chromatic number of the $l$-th power of $H$ is equal to $q_1 q_2 \ldots q_{l}$, where $(h,1,\ldots,1)$ is of dimension $l$. We prove further that, under the same condition, these four invariants take the same value on any subgraph $G$ of $H$ which contains $K$ and the chromatic number of the $l$-th power of $G$ is equal to $q_1 q_2 \ldots q_{l}$. All these results apply in particular to the class of Hamming graphs.