{
  "id": "2006.09690",
  "version": "v1",
  "published": "2020-06-17T07:15:09.000Z",
  "updated": "2020-06-17T07:15:09.000Z",
  "title": "Distance-constrained labellings of Cartesian products of graphs",
  "authors": [
    "Anna Lladó",
    "Hamid Mokhtar",
    "Oriol Serra",
    "Sanming Zhou"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-17T07:15:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C78"
    ],
    "keywords": [
      "cartesian products",
      "distance-constrained labellings",
      "th power",
      "chromatic number",
      "non-trivial graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}