# Distance Two Surjective Labelling of Paths and Interval Graphs

Authors: Sk Amanathulla; G. Muhiuddin; D. Al-Kadi; Madhumangal Pal
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## 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.


---

## Body

## 1. Introduction

The frequency assignment problem is bottomed from the problems of distance labelling of graph. In 1992,L2,1-labelling was invented by Griggs and Yeh [1] in conjunction with channel assigning problem in a multihop radio network.For any graphG=V,E, an L2,1-labelling is a mapping φ:VG⟶1,2,…,, so that φu−φv≥2 if du,v=1 and φu−φv≥1 if du,v=2. The span of L2,1-labelling of G is maxφv:v∈V. The L2,1-labelling number λ2,1G of G is the smallest natural number p so that G has an L2,1-labelling of span p.A surjectiveL2,1-labelling of G=V,E is a mapping φ:V⟶1,2,…,n so that φu−φv≥2 when du,v=1 and φu−φv≥1 when du,v=2, and it requires that each label, 1,2,…,n, be used only once, where n is the number of nodes of G.In Figure1, we have shown an L2,1-labelling of a path with 5 nodes and Figure 2 shows SL21-labelling of the same graph. In Figure 1, identical label is used several times but in Figure 2 the labels 1 to 5 are used only once. So, in SL21-labelling, there is a more complex task compared to L2,1-labelling.Figure 1
L2,1-labelling of a path with five nodes.Figure 2
SurjectiveL2,1-labelling of a path with five nodes.In 1994, Sakai has proved some results regarding distance two labelling of chordal graph. Later, in 2007, Bertossi and Bonuccelli have studied approximateLδ1,δ2,…,δt-coloring of trees and interval graphs. Amanathulla and Pal have studied a lot of problems regarding labelling of graphs, like L3,2,1-labelling problems on permutation graphs [2], Lh1,h2,…,hm-labelling problems on interval graphs [3], Lh1,h2,…,hm-labelling problems on circular-arc graphs [4], L1,1,1- and L1,1,1,1-labelling problems of square of paths [5], and L3,1,1-labelling numbers of squares of paths, complete graphs, and complete bipartite graphs [6]. In 2019, Berhe and Wang have studied computation of certain topological coindices of graphene sheet and C4C8(S) nanotubes and nanotorus [7]; also, Goyal et al. [8] have studied new composition of graphs and their Wiener indices. Hosamani et al. [9] have studied graphs with equal dominating and c-dominating energy. Very recently, B. M. Gurevich has published one paper regarding classes of infinite loaded graphs with randomly deleted edges [10] and Ranjini et al. have studied degree sequence of graph operator for some standard graphs [11]. For general graph, λ2,1G≥Δ+1. In 1992, Griggs et al. showed that λ2,1G≤Δ2+2Δ and have proposed a conjecture [1].In 1993, Jonas [12] has shown that λ2,1G≤Δ2+2Δ−4. Chang et al. [13] have showed λ2,1G≤Δ2+Δ. Král’ and Skrekovski [14] proved that λ2,1G≤Δ2+Δ−1 and they further improved it to λ2,1G≤Δ2+Δ−2 [15].Different bounds forλh1,h2,…,hnG were obtained for different classes of graphs. Some results regarding upper bound of Lh1,h2,…,hn-labelling are shown in Table 1.Table 1
Different types of graphs and their upper bounds.
GraphsLh,k-labelling numbersGeneral graphs0≤λ0,1≤Δ2−Δ [16]Δ≤λ1,1≤Δ2 [17]Δ+1≤λ2,1≤Δ2+Δ−2 [1, 15]λ3,2,1G≤Δ3+2Δ [18]λ4,3,2,1G≤Δ3+2Δ2+6Δ [19]Pathsλ0,1Pn=0or1 [20]λ1,1Pn  = 1 or 2 [21]λ2,1Pn  = 2, 3 or 4 [1]λ3,2,1Pn  = 0, 3, 5, 6 or 7 [22]Ford≥4, λd,2,1Pn  = 0, d, d + 2 or d + 4 [22]Forn≥2λ4,3,2,1Pn  = 5, 8, 9, 11 or 12 [23]CyclesForn≥3, λ0,1Cn  = 1 or 2 [16]Forn≥3, λ1,1Cn  = 2 or 3 [21]Forn≥3, λ2,1Cn=4 [1]For,n≥3, λ3,2,1Cn  = 6, 7, 8 or 9 [22]For,n≥4, d≥5, λd,2,1Cn  = d + 4, d + 6, 2d + 1 or 2d [22]For,n≥3, λ4,3,2,1Cn  = 9, 11, 14 or 13 [23]Completeλ1,1kn=n−1 [24]λd,2,1Kn=dn−1+1 [22]Complete bipartiteλ1,1Km,n=m+n−1 [24]λd,2,1Km,n=d+2m+n−3 [22]Planarλ1,1G≤⌈5/3Δ+1⌉+77 [25]λ2,1G≤2Δ+35 [26]λ2,1G≤5/3Δ+95 [25]λh,kG≤k⌈5/3Δ⌉+18h+77k−18 [25]λ3,2,1G≤15Δ2−Δ+1 [27]Intervalλ2,1G≤Δ+w [28]λh,kG≤max⋅h,2kΔ [29]λ3,2,1G≤6Δ−3 [30]λ4,3,2,1G≤10Δ−6 [30]Circular-arcλ0,1G≤Δ [31]λ1,1G≤2Δ [31]λh,kG≤max⋅h,2kΔ+hω [29]λ2,1G≤Δ+3w [32]λ3,2,1G≤9Δ−6 [33]λ4,3,2,1G≤16Δ−12 [33]Permutationλ0,1G≤2Δ−2 [34]λ0,1G≤Δ−1 [35]λ2,1G≤max4Δ−2,5Δ−8 [36]λ2,1G≤5Δ−2 [34]In [37], Lingscheit et al. investigated minimal and surjective labelling for path, cycle, complete graph, caterpillar, and complete bipartite graph. They have shown that Pn can be surjectively L3,2,1-labelled when n≥7. Very recently, Amanathulla and Pal have studied SL21-labelling of cycle and circular-arc graph CAG and obtained good results for it [38].L2,1-labelling of graphs is a rapidly studied problem for its applications in various fields, especially in channel assignment in radio network. In L2,1-labelling, although there is a light chance to overlap the frequencies in radio network, it cannot be neglected, but in SL21-labelling there is no chance to overlap the frequencies, as in this case the labels are distinct. For this reason, in the recent year, SL21-labelling of graph has become a well-studied problem due to its applications. This motivates us to consider SL21-labelling of paths and IGs. Recently, many researchers applied various related concepts on graphs in different aspects (see, e.g., [39–43]).In the present article, it is shown that any pathPn is surjectively labelled by L2,1-labelling if n≥4 and it also shown that any IG having n nodes can be surjectively L2,1-labelled if n=3Δ−1. Two polynomial time algorithms are also established to label a path and an IG by SL21-labelling.The remainder of this article is organized as follows: inSection 2, some notations and preliminary definitions are given. In Section 3, SL21-labelling of path has been presented. In Section 4, SL21-labelling of IG is investigated. The last section presents concluding remarks.


## 2. Preliminaries and Notations

A path is a graphG=V,E, where vj,vj+1∈E, for all 1≤j≤n−1, where V=v1,v2,…,vn, and it is denoted by Pn. Here, we consider IGIG which is not a path, so Δ>2, because if Δ=2, then it may be a path.Let the set of intervals in real line beI=I1,I2,…,In, where Ik=lk,rk, k=1,2,…,n, lk, and rk are the left and right endpoints of Ik. For any interval Ik,k=1,2,…,n, we draw a node vk, and two nodes vp and vq have joined by a line segment that if the corresponding intervals have common portion, then we obtain an IG [44]. Throughout the paper, an interval Ik and a node vk are the same. An IG and its interval representation are shown in Figure 3.Figure 3
An interval representation and its correspondingIG.Notations. For any IGG with n nodes and corresponding set of intervals I=I1,I2,…,In, we define the following:(1)
LsIk: the set of used SL21-labels which are used before labelling the interval Ik, for every interval Ik∈I.(2)
LiIk: the set of used SL21-labels at distance ii=1,2 from the interval Ik, before labelling Ik, for every Ik∈I.(3)
Lvl1,Ik: the set of valid labels for the interval Ik before labelling Ik, satisfying the adjoining condition of L2,1-labelling, for every interval Ik∈I.(4)
Lvl2,Ik: the valid set of labels of the interval Ik before labelling Ik, satisfying L2,1-labelling condition, for every interval Ik∈I.(5)
LsvlIk: the set of valid SL21-labels of the interval Ik before labelling Ik, for every interval Ik∈I.(6)
λ2,1G: L2,1-labelling number of G.(7)
fjs: the SL21-label of the interval Ij∈I.(8)
Ls: the set of labels after completion of SL21-labelling of G.


## 3. SurjectiveL2,1-Labelling of Paths

In this portion, we have presentedSL21-labelling of path and have showed that any path Pn is surjectively L2,1-labelled if n≥4. Also, we have presented a greedy algorithm to label a path by SL21-labelling.Theorem 1.
ForPn,(1)λ2,1Pn=1,ifn=1,3,ifn=2,4,ifn=3.Proof.
LetPn be a path having n nodes.Case 1:n=1.This result holds trivially.Case 2:n=2.The labels used are 1 and 3 and henceλ2,1P2=3.Case 3:n=3.There are two possible cases shown in Figures4(a) and 4(b). The labelling sequences are 3,1,4 and 1,4,2. From the above result, it is concluded that Pn can be SL21-labelled for n=1,2,3.Figure 4
A path with three nodes and their surjective labels.
(a)(b)Theorem 2.
The minimum path that can be labelled bySL21-labelling is P4.Proof.
From Theorem1, we have λ2,1P2=3 and λ2,1P3=4, so, for n<4, a path Pn cannot be labelled by SL21-labelling. The labelling pattern 3,1,4,2 of path P4 (see Figure 5) shows that P4 can be labelled by SL21-labelling. Hence, P4 is the minimum path that can be labelled by SL21-labelling (Figure 6).Figure 5
A pathP4 labelled by SL21-labelling.Figure 6
(a) A path with of 14 nodes; (b) the path after rearrangement of the nodes.
(a)(b)For this path, the nodeV=v1,v2,…,v22. Here, n>4, so this path can be surjectively labelled by L2,1-labelling. fks is the SL21-label of the node vk, for k=1,2,…,22.According to Algorithm1, we rearrange the nodes as follows:v2=v3, v3=v5, v4=v7, v5=v9, v6=v11, v7=v13, v8=v15, v9=v17, v10=v19, v11=v21, v12=v4, v13=v6, v14=v8, v15=v10, v16=v12, v17=v14, v18=v16, v19=v18, v20=v20, v21=v22, v22=v2, and v1 remains unchanged.Now, nodevk is labelled by k; that is, fks=k, for each k=1,2,…,22. After completion of surjective L2,1-labelling of P22, the node and the label of the corresponding node are shown in Figure 7(b).Algorithm 1: AMPSPL21.
Input: The nodes of the path Pnn>6, V=v1,v2,…,vn.Output: The SL21-label of the path Pn.Step 1: Rearrange the intervals as follows:Case I:n is oddvn=v2;vi+1=v2i+1, for i=1,2,…,n−1/2;vi+n−1/2=v2i, for i=2,3,…,n−1/2;v1 remains same;Case II:n is evenvn=v2;vi+1=v2i+1, for i=1,2,…,n/2−1;vi+n/2−1=v2i, for i=2,3,…,n/2;v1 remain same;Step 2: Label the node vi by i, i.e., fis=i, for i=1,2,…,nendAMPSL21.Figure 7
A path labeled by SL21-labelling.
(a)(b)


## 4. SurjectiveL(2, 1)-Labelling of IGs

Here, some lemmas that we have used to develop the proposed algorithm are presented.Lemma 1.
For anyIGG, L2Ik≤Δ−1, for Ik∈I.Proof.
LetG be an IG having n nodes. The labelling of G starts from the leftmost interval. Let node vk be corresponding to the interval Ik of the IGG. Suppose that in a stage the intervals I1,I2,…,Ik−1 (for some k=2,3,4,…,n) are previously labelled by SL21-labelling and the remaining intervals are unlabelled.
LetL2Ik=p. This means that the number of distinct SL21-labels used for labelling distance two intervals from the interval Ik before labelling Ik is p. Since the degree of the IGG is Δ, there exists an interval Iα (see Figure 8) and those are adjoining to Δ intervals at most. In Figure 8, Iα is adjoining to Ik,Iβ,Ik21,Ik22. Among the intervals, some intervals (Iβ,Ik21,Ik22 in Figure 8) are of distance two apart from Ik and among the intervals there is an interval (Ik in Figure 8) whose distance is not two from Ik. Hence, p≤Δ−1; that is, L2Ik≤Δ−1.Figure 8
A set of intervals.Observation 1.
For anyIGG, LiIk⊆LsIk, for any interval Ik, i=1,2.Observation 2.
For anyIGG, L1Ik≤Δ, for any interval Ik∈I.Theorem 4.
AnyIGG with n nodes is surjectively L2,1-labelled if n=3Δ−1.Proof.
SinceG has n nodes, let I=I1,I2,…,In. Since we want to label the intervals of an IG by SL21-labelling, every label is used exactly once and the labels must be in 1,2,…,n. So,(2)λ2,1G≤2L1Ik+L2Ik≤2Δ+Δ−1,by Lemma1≤3Δ−1.
Again, sinceG has n nodes, to label the whole graph by SL21-labelling, n distinct labels must be required. Also, since λ2,1G≤3Δ−1, in the extreme unfavorable cases 3Δ−1 labels are required to label graph G by L2,1-labelling. Again, in SL21-labelling, the highest label is equal to n. Hence, an IGG is surjectively labelled using L2,1-labelling if n=3Δ−1.
Ifn≠3Δ−1, then the IG may or may not be labelled by SL21-labelling, because in the worst case 3Δ−1 labels are required to label the IG, which is not equal to n. This contradicts the condition that the used label must belong to 1,2,…,n and the highest label must be equal to n for SL21-labelling.


### 4.1. Algorithm for SurjectiveL(2, 1)-Labelling of IGs

In this part, two algorithms are designed: one is to computeLvlk,Ij and the other is to compute SL21-label for an IG (Algorithm 2).Algorithm 2:AMPKVL.
Input:Ik, L1Ik,L2Ik and LsIk, k=2,3,…,n.Output:Lvlp,Ik for p=1,2; k=2,3,…,n.Step 1: for i=1 to r, where r=maxLsIk+2forj=1 to L1Ikletlj be the j th element of L1Ikifi−lj≥2, then add i to the set Lvl1,Ik;end for;end for;Step 2: for m=1 to Lvl1,Ikforn=1 to L2Iklm and pn be the elements of Lvl1,Ik and L2Ik respectively;iflm−pn≥1, then add lm to the set Lvl2,Ik;end for;end for;endAMPKVL.Lemma 2.
Lvlp,Ik for p=1,2 is correctly computed by Algorithm 2 and the time complexity of the above algorithm is OΔ2.Proof.
According to Algorithm2, each element i∈Lvl1,Ij differs from lr by at least 2 for each lr∈L1Ik. Therefore, i−lr≥2 for all i∈Lvl1,Ik and for all lr∈L1Ik. So, Algorithm 2 correctly computes the set Lvl1,Ik for each Ik∈I, k=2,3,…,n. Again, each element lα of Lvl2,Ik differs from lβ by at least 1 for each lβ∈L2Ik. Therefore, lm−pn≥2 for all lm∈Lvl2,Ik and for all pn∈L1Ik, and lm−pn≥1 for all lm∈Lvl2,Ik and for all pn∈L2Ik. Therefore, Algorithm 2 correctly computes Lvlp,Ik for every k=1,2. As Ls is the cardinality of the set of labels Ls, LiIk≤Ls for i=1,2 and Ik∈I, and also r≤3Δ+1, where r=maxLsIk+2. So, Lvl1,Ik is computed by using at most 3Δ+1Ls times, that is, using OΔLs times. Again, Lvl2,In≤3Δ+1, so, Lvl2,Ik is computed using at most 3Δ+1Ls times, that is, using OΔLs times. Since Ls≤3Δ+1, the iterative time for algorithm SLKVL is OΔ2.Lemma 3.
For eachIGG, Lvl1,Ik is the nonempty largest set satisfying distance one condition of L2,1-labelling, l≤r, for every l∈Lvl1,Ik, and r=maxLsIk+2, for any Ik∈I.Proof.
Sincer=maxLsIk+2 and L1Ik⊆LsIk (by Observation 1), r−li≥2 for every li∈L1Ik. Therefore, r∈Lvl1,Ik, so, Lvl1,Ik is a nonempty set. Also, let B be an arbitrary set of labels, which satisfies distance one condition of L2,1-labelling, l≤r, for all l∈B, and r=maxLsIk+2. Then, for b∈B, b−li≥2 for any li∈L1Ik. Thus, b∈Lvl1,Ik. So, b∈B⇒b∈Lvl1,Ik. Then, B⊆Lvl1,Ik. Since B is arbitrary, Lvl1,Ik is the largest nonempty set of labels which satisfies distance one condition of L2,1-labelling, l≤r, for every l∈Lvl1,Ik, and r=maxLsIk+2, for any Ik∈I.Lemma 4.
For anyIGG, Lvl2,Ik is the nonempty largest set satisfying L2,1-labelling condition, l≤r, for every l∈Lvl1,Ik, r=maxLsIk+2, and Ik∈I.Proof.
Sincer=maxLsIk+2 and LiIk⊆LsIk, for i=1,2 (by Observation 1), r−lp≥2 for lp∈LiIk, i=1,2; that is, r−lp≥2 for all lp∈L1Ik and r−lp≥1 for all lp∈L2Ik. Hence, r is the valid L2,1-label of Ik; therefore, r∈Lvl2,Ik. This shows that Lvl2,Ik is a nonempty set. Also, let B be an arbitrary set of labels which satisfies L2,1-labelling conditions, l≤r for every l∈B, and r=maxLsIk+2. Then, for b∈B, b−lp≥2 for lp∈L1Ik and b−lq≥1 for any lq∈L2Ik . Thus, b∈Lvl2,Ik. Thus, b∈B⇒b∈Lvl2,IK. So, B⊆Lvl2,Ik. Since B is arbitrary, Lvl2,Ik is the largest nonempty set of labels which satisfies L2,1-labelling, l≤r for every l∈Lvl2,Ik, and r=maxLsIk+2, for any Ik∈I (Algorithm 3).Algorithm 3: AMPSL21.
Input: The intervals of an IGI=I1,I2,…,In and Lvlp,Ik for k=2,3,…,n and p=1,2 where n=3Δ−1.Output:fks, the SL21-label of the interval Ik, k=1,2,…,n.Step 1: Rearrange the intervals as follows:Case I:n is oddIn=I2;Ii+1=I2i+1, for i=1,2,…,n−1/2;Ii+n−1/2=I2i, for i=2,3,…,n−1/2;I1 remains same;Case II:n is evenIn=I2;Ii+1=I2i+1, for i=1,2,…,n/2−1;Ii+n/2−1=I2i, for i=2,3,…,n/2;I1 is unchanged;Step 2: (Initialization)f1s=1;LsI2=1;Step 3: for k=2 to n−1LsvlIk=Lvl2,Ik−LsIk;fks=minLsvlIk;LsIk+1=LsIk∪fks;end for;Step 4:LsvlIn=Lvl2,In−LsIn;fns=minLsvlIn;Step 5:Ls=LsIn∪fns;endAMPSL21.Theorem 5.
Algorithm3 correctly labels an IG by SL21-labelling, where n=3Δ−1.Proof.
LetG be an IG with n nodes such that n=3Δ−1. We rearranged the nodes so that no two consecutive intervals are adjacent to each other. After rearrangement of the intervals, let I=I1,I2,…,In and let f1s=1 and LsI2=1.
We consider circumstances in which the intervalsI1,I2,…,Ik−1 are already labelled for k=2,3,…,n and the remaining intervals are not labelled. In this stage, our aim is to label Ik by SL21-labelling. Now, Lvl2,Ik is the nonempty largest set of labels satisfying L2,1-labelling, l≤r for any l∈Lvl2,Ik, and r=maxLsIk+2 for every Ik∈I (by Lemma 4).
Again,LsvlIk=Lvl2,Ik−LsIk, so LsvlIk is the nonempty largest set satisfying SL21-labelling, as the label in LsvlIk was not used previously to label any interval and also satisfies L2,1-labelling. Therefore, fks=q, where q=minLsvl2,Ik. Since LsvlIk is the largest set of labels satisfying SL21-labelling, q is the least surjective label of Ik. Since λ2,1G≤3Δ−1, the label of Ik must be less than or equal to 3Δ−1. Again, since n=3Δ−1, the interval Ik is labelled by using only the labels from 1,2,…,n which have not been used earlier to label any interval. Since Ik is arbitrary, any IG is surjectively labelled by L2,1-labelling by Algorithm 3.Theorem 6.
The running time of Algorithm3 is OnΔ3, where n=3Δ−1.Proof.
According to Algorithm3, the SL21-label of Ik, that is, fks, is computed if the set LsvlIk is computed. Now by Lemma 2 we see that by algorithm AMPSL21 one can compute the set Lvlp,Ik, p=1,2, by using OΔ2 time. Again, by Appendix, algorithm AdiffB, Lvl2,Ik−LsIk have been computed in OΔ time, for any k. Therefore, the time needed for computing LsvlIk is OΔ3. Since we need to find Lsvl2,Ik for k=2,3,…,n, the time complexity for Algorithm 3 is On−1Δ3, that is, OnΔ3.


#### 4.1.1. Illustration of AlgorithmAMPSL21

We take anIG having 14 nodes (see Figure 9) and label that graph by Algorithm 3. The graph after completion of surjective L2,1-labelling is given in Figure 10.Figure 9
AnIG.Figure 10
AnIG labelled by SL21-labelling.For the above graph, the set of intervalsI=I1,I2,…,I14 and Δ=5. Here, 3Δ−1=14=n, so this IG can be surjectively labelled by L2,1-labelling. fks is the SL21-label of the interval Ik, for k=1,2,…,14.According to Algorithm3, at first, we rearrange the intervals as follows:I2=I3, I3=I5, I4=I7, I5=I9, I6=I11, I7=I13, I8=I4, I9=I6, I10=I8, I11=I10, I12=I12, I13=I14, I14=I2, and I1 remains the same.f1s=1 and LsI2=1 are also initialized.Iteration 1: For k=2,L1I2=1, L2I2=ϕ.Lvl1,I2=1,2,3, Lvl2,I2=1,2,3.So,LsvlI2=Lvl2,I2−LsI2=1,2,3−1=2,3.Therefore,f2s=minLsvlI2=2.LsI3=LsI2∪f2s=1∪2=1,2.Iteration 2: For k=3,L1I3=1, L2I3=ϕ.Lvl1,I3=3,4, Lvl2,I3=3,4.So,LsvlI3=Lvl2,I3−LsI3=3,4−1,2=3,4.Therefore,f3s=minLsvlI3=3.LsI4=LsI3∪f3s=1,2,3.Iteration 3: For k=4,L1I4=ϕ, L2I4=ϕ.Lvl1,I4=1,2,3,4,5, Lvl2,I4=1,2,3,4,5.So,LsvlI4=Lvl2,I4−LsI4=1,2,3,4,5−1,2,3=4,5.Therefore,f4s=minLsvlI4=4.LsI5=LsI4∪f4s=1,2,3,4.Iteration 4: For k=5,L1I5=1,3, L2I5=ϕ.Lvl1,I5=5,6, Lvl2,I5=5,6.So,LsvlI5=Lvl2,I5−LsI5=5,6−1,2,3,4=5,6.Therefore,f5s=minLsvlI5=5.LsI6=LsI5∪f5s=1,2,3,4,5.Iteration 5: For k=6,L1I6=4, L2I6=ϕ.Lvl1,I6=1,2,6,7, Lvl2,I6=1,2,6,7.So,LsvlI6=Lvl2,I6−LsI6=1,2,6,7−1,2,3,4,5=6,7.Therefore,f6s=minLsvlI6=6.LsI7=LsI6∪f6s=1,2,3,4,5,6.In this way,f7s=7, f8s=8, f9s=9, f10s=10, f11s=11, f12s=12, f13s=13, and, finally, f14s=14.The nodes and their corresponding labels are shown in Table2.Table 2
Nodes and their corresponding surjective L(2,1)-labels.
Nodesv1v2v3v4v5v6v7v8v9v10v11v12v13v14SurjectiveL2,1-labels1234567891011121314


## 4.1. Algorithm for SurjectiveL(2, 1)-Labelling of IGs

In this part, two algorithms are designed: one is to computeLvlk,Ij and the other is to compute SL21-label for an IG (Algorithm 2).Algorithm 2:AMPKVL.
Input:Ik, L1Ik,L2Ik and LsIk, k=2,3,…,n.Output:Lvlp,Ik for p=1,2; k=2,3,…,n.Step 1: for i=1 to r, where r=maxLsIk+2forj=1 to L1Ikletlj be the j th element of L1Ikifi−lj≥2, then add i to the set Lvl1,Ik;end for;end for;Step 2: for m=1 to Lvl1,Ikforn=1 to L2Iklm and pn be the elements of Lvl1,Ik and L2Ik respectively;iflm−pn≥1, then add lm to the set Lvl2,Ik;end for;end for;endAMPKVL.Lemma 2.
Lvlp,Ik for p=1,2 is correctly computed by Algorithm 2 and the time complexity of the above algorithm is OΔ2.Proof.
According to Algorithm2, each element i∈Lvl1,Ij differs from lr by at least 2 for each lr∈L1Ik. Therefore, i−lr≥2 for all i∈Lvl1,Ik and for all lr∈L1Ik. So, Algorithm 2 correctly computes the set Lvl1,Ik for each Ik∈I, k=2,3,…,n. Again, each element lα of Lvl2,Ik differs from lβ by at least 1 for each lβ∈L2Ik. Therefore, lm−pn≥2 for all lm∈Lvl2,Ik and for all pn∈L1Ik, and lm−pn≥1 for all lm∈Lvl2,Ik and for all pn∈L2Ik. Therefore, Algorithm 2 correctly computes Lvlp,Ik for every k=1,2. As Ls is the cardinality of the set of labels Ls, LiIk≤Ls for i=1,2 and Ik∈I, and also r≤3Δ+1, where r=maxLsIk+2. So, Lvl1,Ik is computed by using at most 3Δ+1Ls times, that is, using OΔLs times. Again, Lvl2,In≤3Δ+1, so, Lvl2,Ik is computed using at most 3Δ+1Ls times, that is, using OΔLs times. Since Ls≤3Δ+1, the iterative time for algorithm SLKVL is OΔ2.Lemma 3.
For eachIGG, Lvl1,Ik is the nonempty largest set satisfying distance one condition of L2,1-labelling, l≤r, for every l∈Lvl1,Ik, and r=maxLsIk+2, for any Ik∈I.Proof.
Sincer=maxLsIk+2 and L1Ik⊆LsIk (by Observation 1), r−li≥2 for every li∈L1Ik. Therefore, r∈Lvl1,Ik, so, Lvl1,Ik is a nonempty set. Also, let B be an arbitrary set of labels, which satisfies distance one condition of L2,1-labelling, l≤r, for all l∈B, and r=maxLsIk+2. Then, for b∈B, b−li≥2 for any li∈L1Ik. Thus, b∈Lvl1,Ik. So, b∈B⇒b∈Lvl1,Ik. Then, B⊆Lvl1,Ik. Since B is arbitrary, Lvl1,Ik is the largest nonempty set of labels which satisfies distance one condition of L2,1-labelling, l≤r, for every l∈Lvl1,Ik, and r=maxLsIk+2, for any Ik∈I.Lemma 4.
For anyIGG, Lvl2,Ik is the nonempty largest set satisfying L2,1-labelling condition, l≤r, for every l∈Lvl1,Ik, r=maxLsIk+2, and Ik∈I.Proof.
Sincer=maxLsIk+2 and LiIk⊆LsIk, for i=1,2 (by Observation 1), r−lp≥2 for lp∈LiIk, i=1,2; that is, r−lp≥2 for all lp∈L1Ik and r−lp≥1 for all lp∈L2Ik. Hence, r is the valid L2,1-label of Ik; therefore, r∈Lvl2,Ik. This shows that Lvl2,Ik is a nonempty set. Also, let B be an arbitrary set of labels which satisfies L2,1-labelling conditions, l≤r for every l∈B, and r=maxLsIk+2. Then, for b∈B, b−lp≥2 for lp∈L1Ik and b−lq≥1 for any lq∈L2Ik . Thus, b∈Lvl2,Ik. Thus, b∈B⇒b∈Lvl2,IK. So, B⊆Lvl2,Ik. Since B is arbitrary, Lvl2,Ik is the largest nonempty set of labels which satisfies L2,1-labelling, l≤r for every l∈Lvl2,Ik, and r=maxLsIk+2, for any Ik∈I (Algorithm 3).Algorithm 3: AMPSL21.
Input: The intervals of an IGI=I1,I2,…,In and Lvlp,Ik for k=2,3,…,n and p=1,2 where n=3Δ−1.Output:fks, the SL21-label of the interval Ik, k=1,2,…,n.Step 1: Rearrange the intervals as follows:Case I:n is oddIn=I2;Ii+1=I2i+1, for i=1,2,…,n−1/2;Ii+n−1/2=I2i, for i=2,3,…,n−1/2;I1 remains same;Case II:n is evenIn=I2;Ii+1=I2i+1, for i=1,2,…,n/2−1;Ii+n/2−1=I2i, for i=2,3,…,n/2;I1 is unchanged;Step 2: (Initialization)f1s=1;LsI2=1;Step 3: for k=2 to n−1LsvlIk=Lvl2,Ik−LsIk;fks=minLsvlIk;LsIk+1=LsIk∪fks;end for;Step 4:LsvlIn=Lvl2,In−LsIn;fns=minLsvlIn;Step 5:Ls=LsIn∪fns;endAMPSL21.Theorem 5.
Algorithm3 correctly labels an IG by SL21-labelling, where n=3Δ−1.Proof.
LetG be an IG with n nodes such that n=3Δ−1. We rearranged the nodes so that no two consecutive intervals are adjacent to each other. After rearrangement of the intervals, let I=I1,I2,…,In and let f1s=1 and LsI2=1.
We consider circumstances in which the intervalsI1,I2,…,Ik−1 are already labelled for k=2,3,…,n and the remaining intervals are not labelled. In this stage, our aim is to label Ik by SL21-labelling. Now, Lvl2,Ik is the nonempty largest set of labels satisfying L2,1-labelling, l≤r for any l∈Lvl2,Ik, and r=maxLsIk+2 for every Ik∈I (by Lemma 4).
Again,LsvlIk=Lvl2,Ik−LsIk, so LsvlIk is the nonempty largest set satisfying SL21-labelling, as the label in LsvlIk was not used previously to label any interval and also satisfies L2,1-labelling. Therefore, fks=q, where q=minLsvl2,Ik. Since LsvlIk is the largest set of labels satisfying SL21-labelling, q is the least surjective label of Ik. Since λ2,1G≤3Δ−1, the label of Ik must be less than or equal to 3Δ−1. Again, since n=3Δ−1, the interval Ik is labelled by using only the labels from 1,2,…,n which have not been used earlier to label any interval. Since Ik is arbitrary, any IG is surjectively labelled by L2,1-labelling by Algorithm 3.Theorem 6.
The running time of Algorithm3 is OnΔ3, where n=3Δ−1.Proof.
According to Algorithm3, the SL21-label of Ik, that is, fks, is computed if the set LsvlIk is computed. Now by Lemma 2 we see that by algorithm AMPSL21 one can compute the set Lvlp,Ik, p=1,2, by using OΔ2 time. Again, by Appendix, algorithm AdiffB, Lvl2,Ik−LsIk have been computed in OΔ time, for any k. Therefore, the time needed for computing LsvlIk is OΔ3. Since we need to find Lsvl2,Ik for k=2,3,…,n, the time complexity for Algorithm 3 is On−1Δ3, that is, OnΔ3.


### 4.1.1. Illustration of AlgorithmAMPSL21

We take anIG having 14 nodes (see Figure 9) and label that graph by Algorithm 3. The graph after completion of surjective L2,1-labelling is given in Figure 10.Figure 9
AnIG.Figure 10
AnIG labelled by SL21-labelling.For the above graph, the set of intervalsI=I1,I2,…,I14 and Δ=5. Here, 3Δ−1=14=n, so this IG can be surjectively labelled by L2,1-labelling. fks is the SL21-label of the interval Ik, for k=1,2,…,14.According to Algorithm3, at first, we rearrange the intervals as follows:I2=I3, I3=I5, I4=I7, I5=I9, I6=I11, I7=I13, I8=I4, I9=I6, I10=I8, I11=I10, I12=I12, I13=I14, I14=I2, and I1 remains the same.f1s=1 and LsI2=1 are also initialized.Iteration 1: For k=2,L1I2=1, L2I2=ϕ.Lvl1,I2=1,2,3, Lvl2,I2=1,2,3.So,LsvlI2=Lvl2,I2−LsI2=1,2,3−1=2,3.Therefore,f2s=minLsvlI2=2.LsI3=LsI2∪f2s=1∪2=1,2.Iteration 2: For k=3,L1I3=1, L2I3=ϕ.Lvl1,I3=3,4, Lvl2,I3=3,4.So,LsvlI3=Lvl2,I3−LsI3=3,4−1,2=3,4.Therefore,f3s=minLsvlI3=3.LsI4=LsI3∪f3s=1,2,3.Iteration 3: For k=4,L1I4=ϕ, L2I4=ϕ.Lvl1,I4=1,2,3,4,5, Lvl2,I4=1,2,3,4,5.So,LsvlI4=Lvl2,I4−LsI4=1,2,3,4,5−1,2,3=4,5.Therefore,f4s=minLsvlI4=4.LsI5=LsI4∪f4s=1,2,3,4.Iteration 4: For k=5,L1I5=1,3, L2I5=ϕ.Lvl1,I5=5,6, Lvl2,I5=5,6.So,LsvlI5=Lvl2,I5−LsI5=5,6−1,2,3,4=5,6.Therefore,f5s=minLsvlI5=5.LsI6=LsI5∪f5s=1,2,3,4,5.Iteration 5: For k=6,L1I6=4, L2I6=ϕ.Lvl1,I6=1,2,6,7, Lvl2,I6=1,2,6,7.So,LsvlI6=Lvl2,I6−LsI6=1,2,6,7−1,2,3,4,5=6,7.Therefore,f6s=minLsvlI6=6.LsI7=LsI6∪f6s=1,2,3,4,5,6.In this way,f7s=7, f8s=8, f9s=9, f10s=10, f11s=11, f12s=12, f13s=13, and, finally, f14s=14.The nodes and their corresponding labels are shown in Table2.Table 2
Nodes and their corresponding surjective L(2,1)-labels.
Nodesv1v2v3v4v5v6v7v8v9v10v11v12v13v14SurjectiveL2,1-labels1234567891011121314


## 4.1.1. Illustration of AlgorithmAMPSL21

We take anIG having 14 nodes (see Figure 9) and label that graph by Algorithm 3. The graph after completion of surjective L2,1-labelling is given in Figure 10.Figure 9
AnIG.Figure 10
AnIG labelled by SL21-labelling.For the above graph, the set of intervalsI=I1,I2,…,I14 and Δ=5. Here, 3Δ−1=14=n, so this IG can be surjectively labelled by L2,1-labelling. fks is the SL21-label of the interval Ik, for k=1,2,…,14.According to Algorithm3, at first, we rearrange the intervals as follows:I2=I3, I3=I5, I4=I7, I5=I9, I6=I11, I7=I13, I8=I4, I9=I6, I10=I8, I11=I10, I12=I12, I13=I14, I14=I2, and I1 remains the same.f1s=1 and LsI2=1 are also initialized.Iteration 1: For k=2,L1I2=1, L2I2=ϕ.Lvl1,I2=1,2,3, Lvl2,I2=1,2,3.So,LsvlI2=Lvl2,I2−LsI2=1,2,3−1=2,3.Therefore,f2s=minLsvlI2=2.LsI3=LsI2∪f2s=1∪2=1,2.Iteration 2: For k=3,L1I3=1, L2I3=ϕ.Lvl1,I3=3,4, Lvl2,I3=3,4.So,LsvlI3=Lvl2,I3−LsI3=3,4−1,2=3,4.Therefore,f3s=minLsvlI3=3.LsI4=LsI3∪f3s=1,2,3.Iteration 3: For k=4,L1I4=ϕ, L2I4=ϕ.Lvl1,I4=1,2,3,4,5, Lvl2,I4=1,2,3,4,5.So,LsvlI4=Lvl2,I4−LsI4=1,2,3,4,5−1,2,3=4,5.Therefore,f4s=minLsvlI4=4.LsI5=LsI4∪f4s=1,2,3,4.Iteration 4: For k=5,L1I5=1,3, L2I5=ϕ.Lvl1,I5=5,6, Lvl2,I5=5,6.So,LsvlI5=Lvl2,I5−LsI5=5,6−1,2,3,4=5,6.Therefore,f5s=minLsvlI5=5.LsI6=LsI5∪f5s=1,2,3,4,5.Iteration 5: For k=6,L1I6=4, L2I6=ϕ.Lvl1,I6=1,2,6,7, Lvl2,I6=1,2,6,7.So,LsvlI6=Lvl2,I6−LsI6=1,2,6,7−1,2,3,4,5=6,7.Therefore,f6s=minLsvlI6=6.LsI7=LsI6∪f6s=1,2,3,4,5,6.In this way,f7s=7, f8s=8, f9s=9, f10s=10, f11s=11, f12s=12, f13s=13, and, finally, f14s=14.The nodes and their corresponding labels are shown in Table2.Table 2
Nodes and their corresponding surjective L(2,1)-labels.
Nodesv1v2v3v4v5v6v7v8v9v10v11v12v13v14SurjectiveL2,1-labels1234567891011121314


## 5. Conclusion

InL2,1-labelling, although there is a light chance to overlap the frequencies in radio network, it cannot be neglected, but in SL21-labelling there is no chance to overlap the frequencies, as in this case the labels are distinct. So, the results about SL21-labelling are clearly welcome. In the entire article, we have proved that a path Pn can be surjectively L2,1-labelled if n≥4. An algorithm is also presented to label a path of n nodes, for n≥7. Also, we have showed that an IGG having n nodes can be surjectively labelled by L2,1-labelling if n=3Δ−1. Also, we have presented an OnΔ3 time algorithm to label an IG by SL21-labelling. If n≠3Δ−1, then the IG may or may not be labelled by SL21-labelling. In the future, we can extend this work to other classes of intersection graph. So, there is a scope for the new research to study surjective labelling of permutation graph, trapezoid graph, and so forth.



---

*Source: 9958077-2021-06-07.xml*