Int. J. of Autonomous and Adaptive Communications Systems   »   2018 Vol.11, No.2

 

 

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, vV (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 > 2k, a generalised Petersen graph P(n, k) is obtained by letting its vertex set be {u1, u2, · · · , un} ∪ {v1, v2, · · · , vn} and its edge set be the union of uiui+1, uivi, vivi+k over 1 ≤ in, 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

 

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

 

Available online: 22 May 2018

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article