文章基本信息

标题：Distance Two Surjective Labelling of Paths and Interval Graphs
本地全文：下载
作者：Sk Amanathulla ; G. Muhiuddin ; D. Al-Kadi 等
期刊名称：Discrete Dynamics in Nature and Society
印刷版ISSN：1026-0226
电子版ISSN：1607-887X
出版年度：2021
卷号：2021
页码：1-9
DOI：10.1155/2021/9958077
出版社：Hindawi Publishing Corporation
摘要：Graph labelling problem has been broadly studied for a long period for its applications, especially in frequency assignment in (mobile) communication system, X -ray crystallography, circuit design, etc. Nowadays, surjective L 2,1 -labelling is a well-studied problem. Motivated from the L 2,1 -labelling problem and the importance of surjective L 2,1 -labelling problem, we consider surjective L 2,1 -labelling ( SL 21 -labelling) problems for paths and interval graphs. For any graph G = V , E , an SL 21 -labelling is a mapping φ : V ⟶ 1,2 , … , n so that, for every pair of nodes u and v , if d u , v = 1 , then φ u − φ v ≥ 2 ; and if d u , v = 2 , then φ u − φ v ≥ 1 , and every label 1,2 , … , n is used exactly once, where d u , v represents the distance between the nodes u and v , and n is the number of nodes of graph G . In the present article, it is proved that any path P n can be surjectively L 2,1 -labelled if n ≥ 4 , and it is also proved that any interval graph IG G having n nodes and degree Δ > 2 can be surjectively L 2,1 -labelled if n = 3 Δ − 1 . Also, we have designed two efficient algorithms for surjective L 2,1 -labelling of paths and interval graphs. The results regarding both paths and interval graphs are the first result for surjective L 2,1 -labelling.