Distance-constrained labellings of Cartesian products of graphs

preprint2022arXivOpen access

Abstract

An L(h1,h2,…,hl)L(h_1, h_2, \ldots, h_l)-labelling of a graph GG is a mapping ϕ:V(G)→{0,1,2,…}ϕ: V(G) \rightarrow \{0, 1, 2, \ldots\} such that for 1≤i≤l1\le i\le l and each pair of vertices u,vu, v of GG at distance ii, we have ∣ϕ(u)−ϕ(v)∣≥hi|ϕ(u) - ϕ(v)| \geq h_i. The span of ϕϕ is the difference between the largest and smallest labels assigned to the vertices of GG by ϕϕ, and λh1,h2,…,hl(G)λ_{h_1, h_2, \ldots, h_l}(G) is defined as the minimum span over all L(h1,h2,…,hl)L(h_1, h_2, \ldots, h_l)-labellings of GG. In this paper we study λh,1,…,1λ_{h, 1, \ldots, 1} for Cartesian products of graphs, where (h,1,…,1)(h, 1, \ldots, 1) is an ll-tuple with l≥3l \ge 3. We prove that, under certain natural conditions, the value of this and three related invariants on a graph HH which is the Cartesian product of ll graphs attain a common lower bound. In particular, the chromatic number of the ll-th power of HH equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of HH which contain a certain subgraph of HH. All these results apply in particular to the class of Hamming graphs: if q1≥⋯≥qd≥2q_1\ge \cdots \ge q_d\ge 2 and 3≤l≤d3\le l\le d then the Hamming graph H=Hq1,q2,…,qdH=H_{q_1,q_2,\ldots ,q_d} satisfies λql,1,…,1(H)=q1q2…ql−1λ_{q_l,1,\ldots,1}(H) = q_1q_2\ldots q_l-1 whenever q1q2…ql−1>3(ql−1+1)ql…qdq_1q_2\ldots q_{l-1}>3(q_{l-1}+1)q_l\ldots q_d. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.