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, 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 > 2k, 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_{n}} and its edge set be the union of u_{i}u_{i+1}, u_{i}v_{i}, v_{i}v_{i+k} over 1 ≤ 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 Int. J. of Autonomous and Adaptive Communications Systems, 2018 Vol.11, No.2, pp.99  112 Available online: 22 May 2018
 
