Title:  Nohole λL (k, k – 1, …, 2,1)labeling for square grid 

Authors:  ID Atta, Soumen, Department of Computer Science and Engineering, University of Kalyani, Kalyani741235, West Bengal, India (Author) ID Goldstein, Stanisław, Faculty of Mathematics and Computer Science, University of Lodz, Banacha 22, PL90235 Lodz, Poland (Author) ID Sinha Mahapatra, Priya Ranjan, Department of Computer Science and Engineering, University of Kalyani, Kalyani741235, West Bengal, India (Author) 
Files: 
This document has no files that are freely available to the public. This document may have a physical copy in the library of the organization, check the status via COBISS. 

Language:  English 

Work type:  Not categorized 

Typology:  1.01  Original Scientific Article 

Organization:  UNG  University of Nova Gorica


Abstract:  Motivated by a frequency assignment problem, we demonstrate, for a fixed positive integer k, how to label an infinite square grid with a possibly small number of integer labels, ranging from 0 to λ −1, in such a way that labels of adjacent vertices differ by at least k, vertices connected by a path of length two receive values which differ by at least k − 1, and so on. The vertices which are at least k + 1 distance apart may receive the same label. By finding a lower bound for λ, we prove that the solution is close to optimal, with approximation ratio at most 9/8. The labeling presented is a nohole one, i.e., it uses each of the allowed labels at least once. 

Keywords:  graph labeling, labeling number, nohole labeling, square grid, frequency assignment problem, approximation ratio 

Year of publishing:  2017 

Number of pages:  919 

Numbering:  3, 63 

PID:  20.500.12556/RUNG8150 

COBISS.SIID:  149321731 

DOI:  10.26485/04596854/2017/67.3/1 

NUK URN:  URN:SI:UNG:REP:UJZTOZLJ 

Publication date in RUNG:  17.04.2023 

Views:  1841 

Downloads:  0 

Metadata:  

:

Copy citation 

   Average score:  (0 votes) 

Your score:  Voting is allowed only for logged in users. 

Share:  

Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. 