Distance two surjective labelling of paths and interval graphs
type: Item
instance of: scholarly article
title: Distance two surjective labelling of paths and interval graphs
zbMATH Open document ID: 1471.05095
DOI: 10.1155/2021/9958077
author: Sk Amanathulla
author: G. Muhiuddin
author: Madhumangal Pal
author: Deena Al-Kadi
published in: Discrete Dynamics in Nature and Society
publication date: 2021-08-12T00:00:00Z
review text: Summary: 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 (\(\mathrm{SL}21\))-labelling) problems for paths and interval graphs. For any graph \(G=(V,E)\), an \(\mathrm{SL}21\)-labelling is a mapping \(\varphi:V\longrightarrow\{1,2, \dots,n\}\) so that, for every pair of nodes \(u\) and \(v\), if \(d(u,v)=1\), then \(|\varphi (u)-\varphi (v)|\geq2\); and if \(d(u,v)=2\), then \(|\varphi(u)-\varphi (v)|\geq1\), and every label \(1,2,\dots,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\geq4\), and it is also proved that any interval graph (IG) \(G\) having \(n\) nodes and degree \(\Delta>2\) can be surjectively \(L(2,1)\)-labelled if \(n=3\Delta-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.
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 7381306
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2021/9958077
OpenAlex ID: W3169545093
cites work: Labelling Graphs with a Condition at Distance 2
cites work: Computation of certain topological coindices of graphene sheet and \(C_4C_8(S)\) nanotubes and nanotorus
cites work: On graphs with equal dominating and c-dominating energy
cites work: On classes of infinite loaded graphs with randomly deleted edges
cites work: Degree sequence of graph operator for some standard graphs
cites work: The $L(2,1)$-Labeling Problem on Graphs
cites work: A Theorem about the Channel Assignment Problem
cites work: On the \(L(p,1)\)-labelling of graphs
cites work: \(L(3,2,1)\)-labeling of graphs
cites work: Q3838194
cites work: A bound on the chromatic number of the square of a planar graph
cites work: Coloring the square of a planar graph
cites work: Q3540508
cites work: \(L(2,1)\)-labeling of interval graphs
cites work: On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
cites work: \(L(3, 2, 1)\)- and \(L(4, 3, 2, 1)\)-labeling problems on interval graphs
cites work: Approximations for -Colorings of Graphs
cites work: \(L(0,1)\)-labelling of permutation graphs
cites work: \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
cites work: A mathematical approach on representation of competitions: competition cluster hypergraphs
description: scientific article; zbMATH DE number 7381306