# OnŁ℘,℘−1,…,1 Labelings of Circulant Graphs

Authors: K. Mageshwaran; Ali Ahmad; Bundit Unyong; G. Kalaimurugan; S. Gopinath
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Anm-Ł℘,℘−1,…,1 labeling of a simple graph G is a mapping τ from the vertex set ∨G to 0,1,…,m such that τu−τv≥℘+1−du,v, ∀u,v∈∨G, where length of the shortest route connecting u and v is represented by du,v. The smallest m for which there exists a m-Ł℘,℘−1,…,1 labeling of G is known as the Ł℘,℘−1,…,1 labeling number of G, and it is described by λ℘G. We define m-Ł′℘,℘−1,…,1 as the same as the m-Ł℘,℘−1,…,1 labeling if τ is one to one. The Ł′℘,℘−1,…,1 labeling number of G represented by λ℘,℘−1,…,1′G and is called minimum span. In this paper, we prove that the circulant graphs with specified generating sets admit m-Ł℘,℘−1,…,1 and m-Ł′℘,℘−1,…,1 labeling and also find λ℘G and λ℘,℘−1,…,1′G. Moreover, we find the Ł℘,℘−1,…,1 labeling number of any simple graph with diameter less than ℘.


---

## Body

## 1. Introduction

LetG be a simple connected graph with finite whose vertex set ∨G and edge set εG with ∨G=α and εG=β. The open neighbouring of v∈∨G is Nv=u∈∨G|dv,u=1. Assigning integer values to the vertices or edges or both subject to the certain rules is called labeling of the graph G. For more about graph labeling, refer the survey [1]. Specially, for graph distance labeling, we refer to [2–5], and we follow [6] for graph theoretic terminology. The frequency assignment problem (FAP) is a process to allocate frequencies to the set of transmitters under the condition that there is no interference between the different transmitters. The aim of the problem is to reduce the span (the variation among lower and higher frequencies) of the allocated frequencies. A good number of graph theoretic methods are used for analyzing FAP and majority of them are NP-hard [7]. Especially, FAP can be modeled as mobile communication, satellite communication, and radio/TV broadcasting. In [8, 9], authors studied the results based on h,k-distance labeling of the graph. Also, Nandi et al. [10] originated and explored the idea of m-Ł℘,℘−1,…,1 labeling of graphs.Throughout this paper, letn,r∈ℤ+ such that 1≤r≤n−1/2,Λ=1,2,…,r,n−1,n−2,…,n−r is the generating set of ℤn. The circulant graph with vertex set ∨G=v0,v1,…,vn−1 and edge set εG=vivi+j:0≤i≤n−1,j∈Λ, the indices i+j being taken as modulo n. This graph is represented by Cirn,Λ.


## 2.m-Ł℘,℘−1,…,1 Labeling of Circulant Graphs

We use the following lemma to obtain the minimum span of am-Ł℘,℘−1,…,1 labeling of a graph. Fact: if τ is m-Ł℘,℘−1,…,1 labeling function with λ℘G=m, then at least one vertex v such that τv=0.Lemma 1.
LetG be a simple graph which allows m-Ł℘,℘−1,…,1 labeling by the function τ with each vertex u∈∨; there exists some v∈∨ such that du,v=t and τu−τv=℘+1−t; then, λ℘G=m.Proof.
Supposeλ℘G<m; then, there exists a m′-Ł℘,℘−1,…,1 labeling function τ′ such that m′<m. Without lack of generalization, m′=m−1, there exist u,v∈∨ such that τu=mandτ′v=m′. By the assumption, there exists u′,v′∈∨; we obtain du,u′=t and dv,v′=t with τu−τu′=℘+1−t≤τ′v−τ′v′, since, by the definition,(1)τu−τu′≤τ′v−τ′v′m−τu′≤m′−τ′v′m−τu′≤m−1+τ′v′.
Clearly,τ′v′≤τu′−1 if there exist u″≠uandv″≠v∈∨ such that du′,u″=t and dv′,v″=t with τu′−τu″=℘+1−t≤τ′v′−τ′v″⇒τ′v″≤τu″−1. Otherwise, we choose u″∈∨, such that τu″=maxτ∨/τu,τu′. Continue this process up to the last vertex; this gives the contradiction to the fact that the distance labeling function is τ′.Lemma 2.
Let℘,n,r∈ℤ+ such that ℘ is even and 1≤r≤n−1/2. Let G=Cirn,Λ, Λ=1,2,…,r,n−1,n−2,…,n−r, and ∨G=v0,v1,…,vn−1. Let H be the induced subgraph of G whose vertex set is any set of r℘/2+1+1 consecutive vertices of ∨G; if G admits the m-Ł℘,℘−1,…,1 labeling, then λH=r℘/2+1−1℘.Proof.
Let we assume that∨H=v0,v1,…,vr℘/2+1A; clearly, at most, the distance between any pair vertices of H is ℘/2+1. Let τ be Ł℘,℘−1,…,2,1 labeling function of G. In general, we assume that τv0=x and τvr℘/2+1=x+℘/2 because of the distance between dv0,vr℘/2+1=℘/2+1. Suppose vh∈H with τvh=x+t∈x,x+℘.Case 1: ift<℘/2,(2)τv0−τvh=t<℘2<℘2+1≤℘+1−dv0,vh.Case 2: ift>℘/2,(3)τvh−τvr℘/2+1=t−℘2<℘2<℘2+1≤℘+1−dvh,vr℘/2+1.Case 3: ift=℘/2, since τ is Ł℘,℘−1,…,2,1 labeling of G, then the following one of the subcase holds.Subcase (i): ifdv0,vh=℘/2+1, then the vertices vh and vr℘/2+1 are adjacent:(4)τvh−τvr℘/2+1=0<℘=℘+1−dvh,vr℘/2+1.Subcase (ii): ifdvr℘/2+1,vh=℘/2+1], then the vertices v0 and vh are adjacent:(5)τv0−τvh=℘2<℘=℘+1−dv0,vh.
This gives the contradiction; clearly, no suchvh exists. This argument leads to any other vertex in H which is labeled with multiple ℘ under the minimum required condition of this labeling. Then, we are starting with 0; we get the minimum span r℘/2+1−1℘. Hence, λH=r℘/2+1−1℘.Similarly, we can derive the succeeding lemma.Lemma 3.
Let℘,n,r∈ℤ+ such that ℘ is odd and 1≤r≤n−1/2. Let G=Cirn,Λ, Λ=1,2,…,r,n−1,n−2,…,n−r, and ∨G=v0,v1,…,vn−1. Let H be the induced subgraph of G whose vertex set is any set of r℘/2+r/2+1, consecutive vertices of ∨G; if G admits the m-Ł℘,℘−1,…,1 labeling, then λH=r℘/2+r/2−1℘.Lemma 4.
LetG be any simple finite graph with n vertices; if ℘>diamG=d, then λ℘G=n−1℘−∑s=1ndvs−1,vs−1, where vs=y∈∨G such that dvs−1,y=maxdvs−1,x:∀x≠vi<s∈∨G, s∈ℕ, and v0 is an any arbitrary vertex of G.Proof.
Let us describe the condition:(6)τvi=i℘−∑s=1ndvs−1,vs−1.
Here, we have to prove that the function isŁ℘,℘−1,…,2,1 labeling and take any arbitrary vertex vi and vj:(7)τvi−τvj≥i℘−∑s=1idvs−1,vs−1−j℘−∑s=1jdvs−1,vs−1≥i−j℘−∑s=jidvs−1,vs−1≥i−j℘−i−jd−1≥i−j℘−d+i−j≥℘−d+1τvi−τvj≥℘+1−dvi,vj.
This shows that the functionτ is Ł℘,℘−1,…,1 labeling. We have to prove that the minimum span of this function; let us consider the vertices in the order v0,v1,…,vn such that(8)τvs−1,vs=℘+1−dvs−1,vs.
This sequence of the vertices shows the minimum span ofŁ℘,℘−1,…,2,1 labeling of the graph G. Hence, λ℘G=n−1℘−∑s=1ndvs−1,vs−1.Theorem 1.
Let℘,n∈ℤ+ with n as even and G=Cirn,Λ, where Λ=1,2,…,n/2−1,n−1,n−2,…,n−n/2−1. Then,(9)λ℘G=n−1℘−n2.Proof.
LetG=Cirn,Λ, with Λ=1,2,…,n/2−1,n−1,n−2,…,n−n/2−1. Let ∨G=v0,v1,v2,…,vn−1 and τ:∨⟶0,∞ be given by(10)τvi=2i℘−i,ifi<n2,2℘−1i−n2+℘−1,ifi≥n2.
Letvi,vj∈∨G with i,j<n/2; then, dvi,vj=1 and τvi−τvj=2℘−1i−2℘−1j≥2℘−1≥℘≥℘+1−dvi,vj.
Letvi,vj∈∨G with i,j<n/2; then, dvi,vj=1 and τvi−τvj=2℘−1i−j≥2℘−1≥℘≥℘+1−dvi,vj.
Letvi,vj∈∨G with i<n/2andj≥n/2; then, dvi,vj=1 or 2 and τvi−τvj=2℘−1i−n/2+℘−1−2i℘+i≥℘1−n+n/2−1≥℘≥℘+1−dvi,vj. Thus, τ is Ł℘,℘−1,…,2,1 labeling function, and Lemma 1 holds the theorem.Example 1.
If℘=4 and n=6, then the circulant graph G=Cir6,1,2,4,5 has Ł℘,℘−1,…,2,1 labeling number λ4G=17. Figure 1 illustrates that the span is sharp.Figure 1
λ4G=17.Theorem 2.
Let℘,n,r∈ℤ+ such that ℘ is even and 1≤r≤n−1/2. Let G=Cirn,Λ with Λ=1,2,…,r,n−1,n−2,…,n−r. If 2r℘/2+1|n, then(11)λ℘G=r℘2+1−1℘+℘2.Proof.
LetG=Cirn,Λ, where Λ=1,2,…,r,n−1,n−2,…,n−r. Let ℓ=n/r℘/2+1, ∨G=v0,v1,v2,…,vn−1, and τ:∨⟶0,∞ by(12)τvi=imodr℘2+1℘,ifir℘/2+1=02,…,ℓ,imodr℘2+1℘+℘2,ifir℘/2+1=1,3,…,ℓ−1.
The distance between arbitrary verticesvi and vj in ∨G is(13)dvi,vj=i−jr,ifi−j≤n2,n−i−jr,ifi−j>n2.Case (i): ifi/r℘/2+1=j/r℘/2+1,(14)τvi−τvj=i−jmodr℘2+1℘.Here,i−jmodr℘/2+1≠0 since i and j are distinct, so 0<i−j<r℘/2+1 because i/r℘/2+1=j/℘/2+1.(15)τvi−τvj=i−jmodr℘2+1℘≥℘≥℘+1−dvi,vj.This satisfied theL℘,℘−1,…,2,1 labeling condition.Case (ii): ifi/r℘/2+1≠j/r℘/2+1.Subcase (a): ifτvi−τvj=i−jmodr℘/2+1℘−℘/2.There exista,b∈ℤ+ such that i−jmodr℘/2+1=a⇒i−j=br℘/2+1+a with 1≤b<ℓ. Hence,(16)dvi,vj=br℘/2+1+ar≥℘2+1,orℓr℘/2+1−br℘/2+1+ar≥℘2+1.Therefore, this implies thatdvi,vj≥℘/2+1:(17)τvi−τvj≥℘2=℘−℘2+1−1≥℘+1−dvi,vj.Subcase (b): ifτvi−τvj=i−jmodr℘/2+1℘.
There exista,b∈ℤ+ such that i−jmodr℘/2+1=a⇒i−j=b℘/2+1+a with 2≤b<ℓ−1. Hence, by equation (13),(18)dvi,vj≥2℘2+1=℘+2,or,ℓr℘/2+1−br℘/2+1+ar≥℘+2.
Therefore,dvi,vj≥℘+2 implies that(19)i−jmodr℘2+1℘≥0≥℘−℘+1−1≥℘+1−℘+1≥℘+1−dvi,vj.
Now, each vertex has some vertex with distance℘/2+1 and absolute difference between those vertices is ℘/2. Hence, by Lemma 1, τ is minimum span function of G; this proves the theorem.Example 2.
If℘=4 and r=2, then the circulant graph G=Cir24,1,2,22,23 has Ł℘,℘−1,…,2,1 labeling number λ4G=22. Figure 2 illustrates that the span is sharp.Figure 2
λ4G=22.Theorem 3.
Let℘,n,r∈ℤ+ such that ℘ is odd and 1≤r≤n−1/2. Let G=Cirn,Λ, where Λ=1,2,…,r,n−1,n−2,…,n−r. If 2r℘/2+r/2|n, then(20)λ℘G=r℘2+r2−1℘+℘2.Proof.
LetG=Cirn,Λ with Λ=1,2,…,r,n−1,n−2,…,n−r. Let ℓ=n/r℘/2+r/2, ∨G=v0,v1,v2,…,vn−1, and τ:∨⟶0,∞ by(21)τi=imodr℘2+r2℘,ifir℘/2+r/2=0,2,…,ℓ,imodr℘2+r2℘+℘2,ifir℘/2+r/2=1,3,…,ℓ−1.
The distance between arbitrary verticesvi and vj in ∨G is(22)dvi,vj=i−jr,ifi−j≤n2,n−i−jr,ifi−j>n2.Case (i): ifi/r℘/2+r/2=j/℘/2+r/2,(23)τvi−τvj=i−jmodr℘2+r2℘.Here,i−jmodr℘/2+r/2≠0, since i and j are distinct, so 0<i−j<r℘/2+r/2 because i/r℘/2+r/2=j/r℘/2+r/2:(24)τvi−τvj=i−jmodr℘2+r2℘≥℘≥℘+1−dvi,vj.This satisfied theL℘,℘−1,…,2,1 labeling condition.Case (ii): ifi/r℘/2+r/2=j/r℘/2+r/2.Subcase (a): ifτvi−τvj=i−jmodr℘/2+r/2℘−℘/2.There exista,b∈ℤ+ such that i−jmodr℘/2+r/2=a⇒i−j=br℘/2+r/2+awith1≤b<ℓ. Hence, by equation (22), we have(25)dvi,vj=br℘/2+r/2+ar≥℘/2+r/2,or,ℓr℘/2+r/2−br℘/2+r/2+ar≥℘2+r2.Therefore,dvi,vj≥℘/2+r/2:(26)τvi−τvj≥℘2≥℘−℘2≥℘+1−dvi,vj.Subcase (b): ifτvi−τvj=i−jmodr℘/2+r/2℘.Leti−jmodr℘/2+r/2=a⇒i−j=br℘/2+r/2+awith2≤b<ℓ−1. Hence, by equation (22),(27)dvi,vj=br℘/2+r/2+ar≥2℘2+r2,orℓr℘/2+r/2−br℘/2+r/2+ar≥2℘2+r2.Therefore,dvi,vj≥2℘/2+r/2>℘.
Thus,τ is Ł℘,℘−1,…,2,1 labeling and λ℘G=r℘/2+r/2−1℘. Now, each vertex has some vertex with distance ℘/2+r/2 and absolute difference between those vertices is ℘/2. Hence, by Lemma 1, τ is minimum span function of G; this proves the theorem.Example 3.
Ifk=3 and r=3, then the circulant graph G=Cir14,1,2,3,11,12,13 has Ł℘,℘−1,…,2,1 labeling number λ3G=19. Figure 3 illustrates that the span is sharp.Figure 3
λ3G=19.


## 3.Ł′℘,℘−1,…,2,1 Labeling of Circulant Graphs

We prove the following theorems for the circulant graphCirn,Λ, Λ=1,2,…,r,n−1,n−2,…,n−r, and 1≤r<n/2 admits L′℘,℘−1,…,2,1 labeling with λ℘,℘−1,…,1′G=n−1.Theorem 4.
Letn,r∈ℤ+ with 1≤r<n/2. If n≥2r+1+1 and r+1|n, then the circulant graph Cirn,Λ, Λ=1,2,…,r,n−1,n−2,…,n−r admits L′2,1 labeling with λ2,1′G=n−1.Proof.
Letn,ℓ∈ℤ+,G=Cirn,Λ be the circulant graph with n≥2r+1+1 where 1≤r<n/2 and ℓ=n/r+1. By the division algorithm, for every vertex v∈∨G, we can write v=vir+1+j, where 0≤i≤ℓ−1,0≤j≤r. By using τ:∨G⟶0,1,…,n−1,(28)τvir+1+j=i+ℓj.
Fori=0,0≤j≤r−1, and 1≤d≤ℓ/2 we have(29)Ndvj=vd−1r+1+j+1,vd−1r+1+j+2,…,vd−1r+1+j+r,vℓ−1+d−1r+1+j+1,vℓ−1+d−1r+1+j+2,…,vℓ−1+d−1r+1+j+r.
Also, for1≤i≤ℓ−1,0≤j≤r−1, and 1≤d≤ℓ/2, we have(30)Ndvir+1+j=vi+d−1r+1+j+1,vi+d−1r+1+j+2,…,vi+d−1r+1+j+r,vi−1+d−1r+1+j+1,vi−1+d−1r+1+j+2,…,vi−1+d−1r+1+j+r.
The functionτ is injective, and the values assigned to ∨G is from 0,1,2,…,n−1. So, for every e=uv∈εG, the difference of the labels τu−τv gets one of the values in the set 1,2,…,n−1. By the function τ, for every u∈∨G and v∈Ndu, we get the difference values τu−τv in the set ℓ+d−1,2ℓ+d−1,…,rℓ+d−1,ℓ−1+rℓ+d−1,ℓ−1+r−1ℓ+d−1,ℓ−1+r−2ℓ+d−1,…,ℓ−1+ℓ+d−1. Since n≥2r+1+1, n/r+1=ℓ which implies ℓ≥2. For ℘=1 and ℘=2, the difference τu−τv≥℘+1−du,v, for all u,v∈∨G. Hence, the function τ is a Ł′2,1-labeling with λ2,1′G=n−1.Theorem 5.
Letn,r∈ℤ+ with 1≤r<n/2. If n≥2r+1+1 and r+1∤n with gcdn,r+1=1, then the circulant graph Cirn,Λ, Λ=1,2,…,r,n−1,n−2,…,n−r, admits Ł′2,1 labeling with λ2,1′G=n−1.Proof.
Letn,ℓ∈ℤ+ and Cirn,Λ be the circulant graph with n≥2r+1+1, where 1≤r<n/2 and ℓ=n/r+1. By the division algorithm, for every vertex v∈∨G, we can write v=vir+1modn, where 0≤i≤ℓ−1,0≤j≤r. Let τ:∨G⟶0,1,…,n−1 by(31)τvir+1modn=ifori=0,1,…,n−1.
For0≤i≤n−1, we have(32)Nvir+1modn=vir+1modn+1,vir+1modn+2,…,vir+1modn+r,vir+1modn+n−1,vir+1modn+n−2,…,vir+1modn+n−r.
Sincegcdn,r+1=1, then the function τ is injective, and the values assigned to ∨G is from 0,1,2,…,n−1. So, for every e=uv∈εG, the difference of the labels τu−τv gets one of the values in the set 1,2,…,n−1. By the function τ, for every u∈∨G, v∈Ndu, and 1≤d≤ℓ/2, we get the difference values τu−τv in the set ℓ+d−1,2ℓ+d−1,…,rℓ+d−1,ℓ−1+rℓ+d−1,ℓ−1+r−1ℓ+d−1,ℓ−1+r−2ℓ+d−1,…,ℓ−1+ℓ+d−1. Since n≥2r+1+1, n/r+1=ℓ which implies ℓ≥2. For ℘=1 and ℘=2, the difference |τu−τv|≥℘+1−du,v for all u,v∈∨G. Hence, the function τ is a Ł2,1-labeling with λ2,1′G=n−1.Theorem 6.
Letn, ℘, r∈ℤ+ with 1≤r<n/2. If n≥℘℘−1r+1−r℘−3, for ℘≥3 and ℘−1r+1|n, then the circulant graph Cirn,Λ, Λ=1,2,…,r,n−1,n−2,…,n−r, admits Ł′℘,℘−1,…,2,1 labeling with λ℘,℘−1,…,2,1′G=n−1.Proof.
Letn, ℘, ℓ∈ℤ+ and G=Cirn,Λ with n≥℘℘−1r+1−r℘−3, where 1≤r<n/2. ℘−1r+1 divides n.
Takeℓ=n/℘−1r+1. By the division algorithm, for every vertex v∈∨G, we can write v=vi℘−1r+1+j, where 0≤i≤ℓ−1,0≤j≤r. Let τ:∨G⟶0,1,…,n−1 by(33)τvi℘−1r+1+j=i+ℓj.
Fori=0,0≤j≤r−1, and 1≤d≤ℓ/2, we have(34)Ndvj=vd−1℘−1r+1+j+1,vd−1℘−1r+1+j+2,…,vd−1℘−1r+1+j+r,vℓ−1+d−1℘−1r+1+j+1,vℓ−1+d−1℘−1r+1+j+2,…,vℓ−1+d−1℘−1r+1+j+r.
Also, for1≤i≤ℓ−1,0≤j≤r−1, and 1≤d≤ℓ/2, we have(35)Ndvi℘−1r+1+j=vi+d−1℘−1r+1+j+1,vi+d−1℘−1r+1+j+2,…,vi+d−1℘−1r+1+j+rvi−1+d−1℘−1r+1+j+1,vi−1+d−1℘−1r+1+j+2,…,vi−1+d−1℘−1r+1+j+r.
The functionτ is injective, and the values assigned to ∨G is from 0,1,2,…,n−1. So, for every e=uv∈εG, the difference of the labels τu−τv gets one of the values in the set 1,2,…,n−1. By the function τ, for every u∈∨G and v∈Ndu, we get the difference values τu−τv in the set ℓ+d−1,2ℓ+d−1,…,rℓ+d−1,ℓ−1+rℓ+d−1,ℓ−1+r−1ℓ+d−1,ℓ−1+r−2ℓ+d−1…,ℓ−1+ℓ+d−1. Since n≥℘℘−1r+1−r℘−3, n/℘−1r+1=ℓ which implies ℓ≥℘. For ℘≥3, the difference τu−τv≥℘+1−du,v, for all u,v∈∨G. Hence, the function τ is a Ł′℘,℘−1,…,1-labeling for ℘≥3 with λ℘,℘−1,…,2,1′G=n−1.


## 4. Conclusion

We show in this study that the circulant graphs with specific generating sets are allowedm-Ł℘,℘−1,…,2,1 labeling and Ł℘,℘−1,…,2,1-labeling. Also, we identified the minimum span of m-Ł℘,℘−1,…,2,1 labeling. However, a major challenge of the problems m-Ł℘,℘−1,…,2,1 labeling and Ł′℘,℘−1,…,1 labeling with minimum span for the arbitrary circulant graphs remains under investigation. Another future work is addressed to find m-Ł℘,℘−1,…,1 and Ł′℘,℘−1,…,2,1 labeling with minimum span for the Cayley graphs.



---

*Source: 6578478-2021-10-19.xml*