Journal article

Distance-constrained labellings of Cartesian products of graphs

Anna Llado, Hamid Mokhtar, Oriol Serra, Sanming Zhou



An L(h1,h2,…,hl)-labelling of a graph G is a mapping ϕ:V(G)→{0,1,2,…} such that for 1≤i≤l and each pair of vertices u,v of G at distance i, we have |ϕ(u)−ϕ(v)|≥hi. The span of ϕ is the difference between the largest and smallest labels assigned to the vertices of G by ϕ, and λh1,h2,…,hl(G) is defined as the minimum span over all L(h1,h2,…,hl)-labellings of G. In this paper we study λh,1,…,1 for Cartesian products of graphs, where (h,1,…,1) is an l-tuple with l≥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 lth powe..

View full abstract

University of Melbourne Researchers


Awarded by Spanish Agencia Estatal de Investigacion

Funding Acknowledgements

We would like to thank the anonymous referees for their helpful comments. Anna Llado and Oriol Serra acknowledge financial support from the Spanish Agencia Estatal de Investigacion under project MTM2017-82166-P. Zhou was supported by the Research Grant Support Scheme of The University of Melbourne, Australia.