Title: New bounds for the L(h, k) number of regular grids

Authors: Tiziana Calamoneri, Saverio Caminiti, Guillaume Fertin

Addresses: Dipartimento di Informatica, Universita degli Studi di Roma 'La Sapienza', Via Salaria 113, Roma 00198, Italy. ' Dipartimento di Informatica, Universita degli Studi di Roma 'La Sapienza', Via Salaria 113, Roma 00198, Italy. ' Laboratoire d'Informatique de Nantes-Atlantique, FRE CNRS 2729, Universite de Nantes, 2 rue de la Houssiniere, BP 92208-44322 Nantes Cedex 3, France

Abstract: For any non-negative real values h and k, an L(h, k)-labelling of a graph G = (V ,E) is a function L : V → R such that |L(u) − L(v)| ≥ h if (u, v) ∈ E and |L(u) − L(v)| ≥ k if there exists w ∈ V such that (u,w) ∈ E and (w, v) ∈ E. The span of an L(h, k)-labelling is the difference between the largest and the smallest value of L. We denote by λ_h,k(G) the smallest real λ such that graph G has an L(h, k)-labelling of span λ. The aim of the L(h, k)-labelling problem is to satisfy the distance constraints using the minimum span. In this paper, we study the L (h, k)-labelling problem on regular grids of degree 3, 4 and 6 for those values of h and k whose λ_h,k is either not known or not tight. We also initiate the study of the problem for grids of degree 8. For all considered grids, in some cases we provide exact results, while in the other ones we give very close upper and lower bounds.

Keywords: L(h, k)-labelling; triangular grids; hexagonal grids; squared grids; octagonal grids; frequency assignment; wireless communication; wireless networks; mobile networks; mobile communications.

DOI: 10.1504/IJMNDI.2006.010811

International Journal of Mobile Network Design and Innovation, 2006 Vol.1 No.2, pp.92 - 101

Published online: 05 Sep 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article