Distance Two Surjective Labelling of Paths and Interval Graphs

Sk Amanathulla, G. Muhiuddin, D. Al-Kadi, Madhumangal Pal and Juan L. G. Guirao

Discrete Dynamics in Nature and Society, 2021, vol. 2021, 1-9

Abstract: 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 L2,1-labelling is a well-studied problem. Motivated from the L2,1-labelling problem and the importance of surjective L2,1-labelling problem, we consider surjective L2,1-labelling (SL21-labelling) problems for paths and interval graphs. For any graph G=V,E, an SL21-labelling is a mapping φ:V⟶1,2,…,n so that, for every pair of nodes u and v, if du,v=1, then φu−φv≥2; and if du,v=2, then φu−φv≥1, and every label 1,2,…,n is used exactly once, where du,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 Pn can be surjectively L2,1-labelled if n≥4, and it is also proved that any interval graph IGG having n nodes and degree Δ>2 can be surjectively L2,1-labelled if n=3Δ−1. Also, we have designed two efficient algorithms for surjective L2,1-labelling of paths and interval graphs. The results regarding both paths and interval graphs are the first result for surjective L2,1-labelling.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/ddns/2021/9958077.pdf (application/pdf)
http://downloads.hindawi.com/journals/ddns/2021/9958077.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:9958077

DOI: 10.1155/2021/9958077

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().