### Title: *L*(*d*,1)-labellings of generalised Petersen graphs

**Authors**: Fei Deng; Xiaoling Zhong; Zehui Shao

**Addresses**: College of Information Science and Technology, Chengdu University of Technology, Chengdu 610059, China ' College of Information Science and Technology, Chengdu University of Technology, Chengdu 610059, China ' School of Information Science and Technology, Chengdu University, Chengdu 610106, China

**Abstract**: An interesting graph distance constrained labelling problem can model the frequency channel assignment problem as well as code assignment in computer networks. The frequency assignment problem asks for assigning frequencies to transmitters in a broadcasting network with the aim of avoiding undesired interference. One of the graph theoretical models of The frequency assignment problem is the concept of distance constrained labelling of graphs. Let *u* and *v* be vertices of a graph *G* = (*V* (*G*),*E*(*G*)) and *d*(*u*, *v*) be the distance between *u* and *v* in *G*. For an integer *d* ≥ 0, an *L*(*d*, 1)-labelling of *G* is a function *f* : *V* (*G*) → {0, 1, · · · } such that for every *u*, *v* ∈ *V* (*G*), |*f*(*u*) − *f*(*v*)| ≥ *d* if *d*(*u*, *v*) = 1 and |*f*(*u*) − *f*(*v*)| ≥ 1 if *d*(*u*, *v*) = 2. The span of *f* is the difference between the largest and the smallest numbers in *f*(*V* (*G*)). The λ_{d,1}-number of *G* is the minimum span over all *L*(*d*, 1)-labellings of *G*. For natural numbers *n* and *k*, where *n* > 2*k*, a generalised Petersen graph *P*(*n*, *k*) is obtained by letting its vertex set be {*u*_{1}, *u*_{2}, · · · , *u _{n}*} ∪ {

*v*

_{1},

*v*

_{2}, · · · ,

*v*} and its edge set be the union of

_{n}*u*

_{i}*u*

_{i+1},

*u*

_{i}*v*,

_{i}*v*

_{i}*v*over 1 ≤

_{i+k}*i*≤

*n*, where subscripts are reduced modulo n. In this paper, we show the λ

_{d,1}-numbers of the generalised Petersen graphs

*P*(

*n*,

*k*) for

*n*≥ 5.

**Keywords**: graph labelling; generalised Petersen graph; code assignment; frequency assignment problem.

**DOI**: 10.1504/IJAACS.2018.092017

International Journal of Autonomous and Adaptive Communications Systems, 2018 Vol.11 No.2, pp.99 - 112

*Received: 31 Aug 2015Accepted: 05 Oct 2015*

*Published online: 22 May 2018**