Article: L(d,1)-labellings of generalised Petersen graphs Journal: International Journal of Autonomous and Adaptive Communications Systems (IJAACS) 2018 Vol.11 No.2 pp.99 - 112 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 {u1, u2, · · · , un} ∪ {v1, v2, · · · , vn} and its edge set be the union of uiui+1, uivi, vivi+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. Inderscience Publishers - linking academia, business and industry through research

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₁, u₂, · · · , u_n} ∪ {v₁, v₂, · · · , v_n} and its edge set be the union of u_iu_i+1, u_iv_i, v_iv_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

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

Received: 31 Aug 2015
Accepted: 05 Oct 2015
Published online: 30 May 2018 *

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

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

Keep up-to-date