Distance-two labellings of Hamming graphs

Let j≥k≥0j≥k≥0 be integers. An ℓℓ-L(j,k)L(j,k)-labelling of a graph G=(V,E)G=(V,E) is a mapping ϕ:V→{0,1,2,…,ℓ}ϕ:V→{0,1,2,…,ℓ} such that |ϕ(u)−ϕ(v)|≥j|ϕ(u)−ϕ(v)|≥j if u,vu,v are adjacent and |ϕ(u)−ϕ(v)|≥k|ϕ(u)−ϕ(v)|≥k if they are distance two apart. Let λj,k(G)λj,k(G) be the smallest integer ℓℓ such that GG admits an ℓℓ-L(j,k)L(j,k)-labelling. Define λ¯j,k(G) to be the smallest ℓℓ if GG admits an ℓℓ-L(j,k)L(j,k)-labelling with ϕ(V)={0,1,2,…,ℓ}ϕ(V)={0,1,2,…,ℓ} and ∞∞ otherwise. An ℓℓ-cyclic L(j,k)L(j,k)-labelling is a mapping ϕ:V→Zℓϕ:V→Zℓ such that |ϕ(u)−ϕ(v)|ℓ≥j|ϕ(u)−ϕ(v)|ℓ≥j if u,vu,v are adjacent and |ϕ(u)−ϕ(v)|ℓ≥k|ϕ(u)−ϕ(v)|ℓ≥k if they are distance two apart, where |x|ℓ=min{x,ℓ−x}|x|ℓ=min{x,ℓ−x} for xx between 0 and ℓℓ. Let σj,k(G)σj,k(G) be the smallest ℓ−1ℓ−1 of such a labelling, and define σ¯j,k(G) similarly to λ¯j,k(G). We determine λ2,0λ2,0, λ¯2,0, σ2,0σ2,0 and σ¯2,0 for all Hamming graphs Kq1□Kq2□⋯□KqdKq1□Kq2□⋯□Kqd (d≥2d≥2, q1≥q2≥⋯≥qd≥2q1≥q2≥⋯≥qd≥2) and give optimal labellings, with the only exception being 2q≤σ¯2,0(Kq□Kq)≤2q+1 for q≥4q≥4. We also prove the following “sandwich theorem”: If q1q1 is sufficiently large then λ2,1(G)=λ¯2,1(G)=σ¯2,1(G)=σ2,1(G)=λ1,1(G)=λ¯1,1(G)=σ¯1,1(G)=σ1,1(G)=q1q2−1 for any graph GG between Kq1□Kq2Kq1□Kq2 and Kq1□Kq2□⋯□KqdKq1□Kq2□⋯□Kqd, and moreover we give a labelling which is optimal for these eight invariants simultaneously.