# OnLh,k-Labeling Index of Inverse Graphs Associated with Finite Cyclic Groups

Authors: K. Mageshwaran; G. Kalaimurugan; Bussakorn Hammachukiattikul; Vediyappan Govindan; Ismail Naci Cangul
Journal: Journal of Mathematics
 (2021)

---

## Abstract

AnLh,k-labeling of a graph G=V,E is a function f:V⟶0,∞ such that the positive difference between labels of the neighbouring vertices is at least h and the positive difference between the vertices separated by a distance 2 is at least k. The difference between the highest and lowest assigned values is the index of an Lh,k-labeling. The minimum number for which the graph admits an Lh,k-labeling is called the required possible index of Lh,k-labeling of G, and it is denoted by λkhG. In this paper, we obtain an upper bound for the index of the Lh,k-labeling for an inverse graph associated with a finite cyclic group, and we also establish the fact that the upper bound is sharp. Finally, we investigate a relation between Lh,k-labeling with radio labeling of an inverse graph associated with a finite cyclic group.


---

## Body

## 1. Introduction

The frequency assignment problem (FAP) interacts with the assignment of frequencies to locations in such a manner that there is no interruption between frequencies allotted to the neighbouring locations while attempting to reduce the index of the allocated frequencies (the difference between the highest and lowest frequency bands). There are plenty of graph theoretical models for solving FAP, but many of them are NP-hard [1]. Specifically, FAP has been represented as a graph labeling problem to allocate frequencies to transceivers in a wireless communication such as a cellular network or a radio network. With the massive growth in the required calls in the network, we must find an effective assessment of frequency in the network having a minimal index. Here, vertices represent the transceivers and lines represent couples of locations that overlap with each other.The motivation for the study ofLh,k-labelings is the allocation of radio frequency of transceivers in the interruption range [2]. This radio frequency problem can be perfectly examined by Lh,k problem. In Lh,k problem, all transceivers are allocated a frequency so that the distinction between the labels of neighbouring transceivers is at leasth and the distinction between transceivers separated by a distance 2 is at least k. The variation between the maximum and minimum allotted values is the index of an Lh,k-labeling. The theoretical explanation of this graph emerges from the problem of allocating frequencies to a wireless network’s transceivers to prevent any form of disruption. The geographical distance and the purpose of the atmosphere in this setting are the main factors that decide the h andk parameters, and h≥k is generally expected. Lh,k-labelings have been studied by various authors, see [3, 4] and survey in [5]. Recently, Mitra and Bhoumik [6] provided an upper bound of the span of three specific cases of circulant graphs. Song et al. [3] proved that the labeling of Lj,k for the complete graph is the direct product. The radio labeling applies to the number of interruption permissible levels considered in the L2,1-labeling from two to the highest allowable diameter of G. The highest allowable distance between every couple of vertices inG is denoted by diamG. In [7], Chartrand presented the idea of radio labeling and discussed the radio number for cycles and paths in [8] by Liu and Zhu. For a detailed survey of graph labelings, one can refer to [9].Since Cayley graphs, many relations between groups and graphs have been established and interest began to be on such relations. The inverse graphs associated with finite groups were recently introduced and analyzed by Alfuraidan and Zakariya [10], as a new example of such relations. They developed some important graph theoretical aspects of the inverse graphs of certain finite groups that really shine as a spotlight on algebraic aspects of the groups. They defined an interconnection in between the algebraic aspects of the finite groups and the graph theoretical aspects of the identified inverse graphs. The inverse graph was utilized to categorize certain problems of isomorphism in finite groups. In the same way, Kalaimurugan and Megeshwaran [11] explored the Zk-magic index on the inverse graph.On the contrary, Ejima et al. [12] had found the inverse graphs of dihedral and symmetric groups. Very recently, some properties of finite group invertible graphs have been investigated by Chalapathi and Kiran-Kumar [13]; invertible graphs have been established and some interesting results on them have been obtained using finite group classification. The chromatic number, girth, clique number, diameter, and size have been calculated for each finite group. Jones and Lawson [8] investigated the inverse graph of the large semigroup of a graph-related topological groupoid and the semigroup analogue called the Leavitt path algebra. Let G be a finite simple connected graph whose vertex set VG and edge set EG with VG=p and EG=q. The open neighbourhood Nv of a vertex v∈VG is the set of all vertices which are adjacent tov. We follow [14] for graph theoretic terminology. Note that the inverse graph of a finite cyclic group G=GSZn is simple and connected. To the best of our observations, for the very first time, we investigate the Lh,k-labeling of the inverse graphs in this paper and we give the exact minimum span of Lh,k-labeling of inverse graphs associated with finite cyclic groups.


## 2. Preliminaries

We now recall some powerful and known results used in the proofs of our new results.Definition 1.
(see [15]). Griggs and Yeh introduced an L2,1-labeling of a graph GV,E as a function f:VG⟶0,1,…,n such that fu−fv≥2 if du,v=1 and fu−fv≥1 if du,v=2, where du,v denotes the shortest path in between the vertices u andv. The minimum index for certain possible functions of L2,1 labeling is indicated by λ2,1G and referred to as λ2,1 number of G.Definition 2.
(see [3]). If h,kh≥k are positive integers, then the Lh,k-labeling of a graph G=V,E is a function f:V⟶0,∞ such that(1)fu−fv≥h,ifdu,v=1,k,ifdu,v=2.
The maximum label attained byf is referred to the index of f. The minimum index for a certain possible function f is the λkh-number of G denoted by λkhG.Definition 3.
(see [7, 8]). A radio labeling of a graph GV,E is a one-to-one function f:V⟶0,∞ such that, for each u,v∈V, fu−fv≥diamG−du,v+1. The index of f is the variation of the highest and the lowest frequencies utilized, that is, maxu,v∈Vfu−fv for each pairs u,v∈V. The radio number of G is the index of a radio labeling of G and is denoted by rnG.Definition 4.
(see [10]). Let Γ,∗ be a finite group and S=u∈Γ|u≠u−1. The inverse graph GSΓ associated with Γ as the graph whose vertex set coincides with Γ such that two different verticesu andv are adjacent iff either uv∈S or vu∈S. When Γ is the cyclic group Zn and S is the set of non-self-inverse elements of Zn, GSΓ is called the inverse graph of a finite cyclic group G=GSZn.Theorem 1.
(see [10]). If Γ is a finite abelian group, which contains three or more elements, and if S is a nonempty subset of the non self-invertible elements, then GSΓ is a connected graph.Theorem 2.
(see [10]). If Γ is an arbitrary finite group, then the inverse graph is not complete.Theorem 3.
(see [10]). A connected inverse graph has diameter two.


## 3. Main Results

We prove the following results on the inverse graphs associated with a finite cyclic group admitting anLh,k-labeling having minimum index.Theorem 4.
Letn≥3 be an odd integer. Then, the inverse graph GSZn admits an Lh,k-labeling with λkhGSZn≤n−1/2h+k and this bound is sharp.Proof.
Sincen is odd, the unique self-invertible element is 0. Let G=GSZn be the inverse graph associated with a finite cyclic group. Let VG=S1∪S2∪S3, where S1=v0, S2=v1,v2,…,vn−1/2, and S3=vn+1/2,vn+1/2+1,vn+1/2+2,…,vn−1. Define the function f:VG⟶0,1,…,n by(2)fvi=0,ifv0∈S1,ih+i−1k,ifvi∈S2,n−ih+k,ifvi∈S3.Case (i): ifv0∈S1 and vj are the elements of S2 (or S3), then dv0,vj=1. We claim that fv0−fvj≥h. For the function f, we have h≤fvi−fvj≤n−1/2h+k.Case (ii): ifviandvj are the elements of S2 (or S3), then dvi,vj=1. We claim that fvi−fvj≥h. We have h+k≤fvi−fvj≤n−3/2h+k≤n−1/2h+k.Case (iii): ifvi∈S2 and vj∈S3−vn−i, then dvi,vj=1 where, j≠n−i. We claim that fvi−fvj≥h. We have h≤fvi−fvj≤n−1/2h+k−h≤n−1/2h+k.Case (iv): ifvi∈S2 and vj=vn−i∈S3, then dvi,vj=2, where j=n−i. We claim that fvi−fvj≥k. We have k≤fvi−fvj. Figure 1 illustrates that the bound on the graph index is sharp.Theorem 5.
Letn be even and h and k be positive integers with k≥⌈h/2⌉. Then, the inverse graph GSZn admits an Lh,k-labeling with(3)λkhGSZn≤n−24h+3k+k,ifn≡2mod4,n4h+3k−k,ifn≡0mod4.
Also, these bounds are sharp.Figure 1
λkhGSZ7=3h+k.Proof.
Case (a): letn≡2mod4. Sincen is even, then the self-invertible elements are 0 and n/2. Let G=GSZn be the inverse graph associated with a finite cyclic group. Let VG=S1∪S2∪S3∪S4∪S5∪S6, where S1=v0S2=v1,v2,…,vn−2/4, S3=vn−2/4+1,vn−2/4+2,…,vn/2−1, S4=vn/2+1,vn/2+2,…,v3n−2/4, S5=v3n−2/4+1,v3n−2/4+2,…,vn−1, and S6=vn/2. Define the function f:VG⟶0,1,…,n. Then,(4)fvi=0,ifv0∈S1,ih+3i−1+1k,ifvi∈S2.n2−ih+3n2−i−1k,ifvi∈S3,i−n2h+3i−n2k,ifvi∈S4,n−ih+3n−i+1k,ifvi∈S5,k,ifvn/2∈S6.Subcase (i): ifviandvj are distinct elements in Sp for all 2≤p≤5, then dvi,vj=1. We claim that fvi−fvj≥h. We have h+3k≤fvi−fvj≤n−6/4h+3k. Clearly, h+3k≥h. Hence, fvi−fvj≥h.Subcase (ii): letvi∈S2 and vj∈S3 with i≠j be the adjacent vertices iff j≠n/2−i. Assume that j≠n/2−i; then, dvi,vj=1. For the function f, we have h+2k≤fvi−fvj≤n−6/4h+3k+k. Clearly, fvi−fvj≥h. If j=n/2−i, then dvi,vj=2. We have k=fvi−fvj. Suppose the element vj∈S4; then, dvi,vj=1. We have h+2k≤fvi−fvj≤n−6/4h+3k+2k. Clearly, fvi−fvj≥h. Suppose the element vj∈S5 and vi adjacent to vj iff j≠n−i. Assume that j≠n−i; then, dvi,vj=1. For the function f, we have h+2k≤fvi−fvj≤n−6/4h+3k+3k. If j=n−i, then dvi,vj=2. By the function f, fvi−fvj=3k≥k.Subcase (iii): ifvi∈S3, then suppose vj∈S4 and vi is adjacent to vj iff j≠n−i. If j≠n−i, then dvi,vj=1. We then have h+4k≤fvi−fvj≤n−6/4h+3k+k. Clearly, fvi−fvj≥h. If j=n−i, then dvi,vj=2. We have fvi−fvj=k. Suppose that vj∈S5; then, dvi,vj=1. We have 2k≤fvi−fvj≤n−2/4h+3k−k. Clearly, k≥⌈h/2⌉ such that 2k≥h. Hence, fvi−fvj≥h.Subcase (iv): letvi∈S4 and vj∈S5vi adjacent to vj iff j≠3n/2−i. j≠3n/2−i, then dvi,vj=1. We then have h+2k≤fvi−fvj≤n−6/4h+3k. Clearly, fvi−fvj≥h. If j=3n/2−i, then dvi,vj=2. We have k=fvi−fvj.Subcase (v): the vertexv0 is not adjacent to vn/2 and dv0,vn/2=2. Now, fvi−fvj=k. The vertex v0 is adjacent to all other vertices. Then, dv0,vj=1, where j≠n/2. We have h+k≤fvi−fvj≤n−2/4h+3k+k. Suppose that the vertex vn/2 is adjacent to all other vertices. Then, dvn/2,vj=1, where j≠0. Now, we have h≤fvn/2−fvj≤n−2/4h+3k.Case (b): ifn≡0mod4. Sincen is even, then the self-invertible elements are 0 and n/2. Let G=GSZn be the inverse graph associated with a finite cyclic group. Let VG=S1∪S2∪S3∪S4∪S5∪S6∪S7∪S8, where S1=v0, S2=v1,v2,…,vn/4−1, S3=vn/4+1,vn/4+2,…,vn/2−1, S4=vn/2+1,vn/2+2,…,v3n/4−1, S5=v3n/4+1,v3n/4+2,…,vn−1, S6=vn/2, S7=vn/4, and S8=v3n/4. Define the function f:VG⟶0,1,…,n. Then,(5)fvi=0,ifv0∈S1,ih+3i−1+1k,ifvi∈S2,n2−ih+3n2−i−1k,ifvi∈S3,i−n2h+3i−n2k,ifvi∈S4,n−ih+3n−i+1k,ifvi∈S5,k,ifvn/2∈S6,n4h+3k−2k,ifvn/4∈S7,n4h+3k−k,ifv3n/4∈S8.
In the casen≡0mod4, we similarly have the following. The vertex vn/4 is not adjacent to v3n/4, and therefore, dvn/4,v3n/4=2. Now, fvi−fvj=k. The vertex vn/4 is adjacent to all other vertices. Then, dvn/4,vj=1, where j≠3n/4. We now have h≤fv0−fvj≤n/4h+3k−2k. Suppose that the vertex v3n/4 is adjacent to all other vertices. Then, dv3n/4,vj=1, where j≠n/4. We have h+k≤fvn/2−fvj≤n/4h+3k−k. Figures 2 and 3 illustrate that the bounds are sharp.Figure 2
λkhGSZ10=2h+7k.Figure 3
λkhGSZ8=2h+5k.Theorem 6.
Letn be even and h andk be positive integers with k<⌈h/2⌉. Then, the inverse graph GSZn admits an Lh,k-labeling with(6)λkhGSZn≤n−22h+n+24k,ifn≡2mod4,n2−1h+n+44k,ifn≡0mod4.
Finally, these bounds are sharp.Proof.
We have the following cases:Case (a): ifn≡2mod4, since n is even, the self-invertible elements are 0 and n/2. Let G=GSZn be the inverse graph associated with a finite cyclic group. Let VG=S1∪S2∪S3∪S4∪S5∪S6, where S1=v0, S2=v1,v2,…,vn−2/4, S3=vn−2/4+1,vn−2/4+2,…,vn/2−1, S4=vn/2+1,vn/2+2,…,v3n−2/4, S5=v3n−2/4+1,v3n−2/4+2,…,vn−1, and S6=vn/2. Define the function f:VG⟶0,1,…,n:(7)fvi=0,ifv0∈S1,2i−1+1h+k,ifvi∈S2,2n2−i−1h+n2−i+1k,ifvi∈S3,i−n22h+i−n2k,ifvi∈S4,n−i2h+n−i+1k,ifvi∈S5,k,ifvn/2∈S6.Subcase (i): ifviandvj are distinct elements in Sp, for all 2≤p≤5, then dvi,vj=1. We claim that fvi−fvj≥h. We have 2h+k≤fvi−fvj≤n−6/42h+k. Clearly, 2h+k≥h. Hence, fvi−fvj≥h.Subcase (ii): letvi∈S2 and vj∈S3 with i≠j be the adjacent vertices iff j≠n/2−i. Assume that j≠n/2−i; then, dvi,vj=1. We have 2h+2k≤fvi−fvj≤n−6/42h+k+k. Clearly, fvi−fvj≥h. If j=n/2−i, then dvi,vj=2. We then have k=fvi−fvj. Suppose that the element vj∈S4; then, dvi,vj=1. We have h≤fvi−fvj≤n−2/42h+3k−h+k. Clearly, fvi−fvj≥h. Suppose that the element vj∈S5, vi is adjacent to vj iff j≠n−i. Assume that j≠n−i, then dvi,vj=1. For the function f, we have h≤fvi−fvj≤n−6/42h+k+h+k. If j=n−i, then dvi,vj=2. Hence, fvi−fvj=h+k≥k.Subcase(iii): Ifvi∈S3, suppose vj∈S4 and vi is adjacent to vj iffj≠n−i. If j≠n−i, then dvi,vj=1. We have h+2k≤fvi−fvj≤n−6/42h+k+h. Clearly, fvi−fvj≥h. If j=n−i, then dvi,vj=2. We have fvi−fvj=h−k. Clearly, k<h/2. Then, 2k<h implies that h−k>k. Hence, fvi−fvj≥k. Suppose that vj∈S5. Then, dvi,vj=1. We have h≤fvi−fvj≤n−6/42h+k+h. Clearly, fvi−fvj≥h.Subcase (iv): letvi∈S4 and vj∈S5 with vi is adjacent to vj iff j≠3n/2−i. j≠3n/2−i; then, dvi,vj=1. We have 2h≤fvi−fvj≤n−6/42h+k+k. Clearly, fvi−fvj≥h. If j=3n/2−i, then dvi,vj=2. We then have k=fvi−fvj.Subcase (v): the vertexv0 is not adjacent to vn/2 and dv0,vn/2=2. Here, fvi−fvj=k. The vertex v0 is adjacent to all other vertices. Then, dv0,vj=1, where j≠n/2. We have h+k≤fv0−fvj≤n−2/2h+n+2/4k. Suppose that the vertex vn/2 is adjacent to all other vertices. Then, dvn/2,vj=1, where j≠0. We have h≤fvn/2−fvj≤n−2/2h+n−2/4k.Case (b): ifn≡0mod4, since n is even, then the self-invertible elements are 0 and n/2. Let G=GSZn be the inverse graph associated with a finite cyclic group. Let VG=S1∪S2∪S3∪S4∪S5∪S6∪S7∪S8, where S1=v0, S2=v1,v2,…,vn/4−1, S3=vn/4+1,vn/4+2,…,vn/2−1, S4=vn/2+1,vn/2+2,…,v3n/4−1, S5=v3n/4+1,v3n/4+2,…,vn−1, S6=vn/2, S7=vn/4, and S8=v3n/4. Define a function f:VG⟶0,1,…,n. Then,(8)fvi=0,ifv0∈S1,2i−1+1h+k,ifvi∈S2,2n2−i−1h+n2,−i+1k,ifvi∈S3,i−n22h+i−n2k,ifvi∈S4,n−i2h+n−i+1k,ifvi∈S5,k,ifvn/2∈S6,n2−1h+n4k,ifvn/4∈S7,n2−1h+n+44k,ifv3n/4∈S8.
The casen≡0mod4 can be dealt similarly as follows. The vertex vn/4 is not adjacent to v3n/4 and dvn/4,v3n/4=2. Then, fvi−fvj=k. The vertex vn/4 is adjacent to all other vertices. Then, dvn/4,vj=1, where j≠3n/4. We have h≤fv0−fvj≤n/2−1h+n/4k. Suppose the vertex v3n/4 is adjacent to all other vertices. Then, dv3n/4,vj=1, where j≠n/4. We hence have h+k≤fvn/4−fvj≤n/2−1h+n+4/4k. Figures 4 and 5 illustrate that the bounds are sharp.Figure 4
λkhGSZ10=4h+3k.Figure 5
λkhGSZ8=3h+3k.


## 4. Relation betweenLh,k and the Radio Labeling

The radio labeling idea is applied to a large number of interruption permissible levels inLh,k-labeling from h to the maximum allowable diameter of G, where h=2 and k=1. By Theorem 3, diamGSZn=2. Hence, the maximum distance is 2 so that the possible distance of GSZn is 1 or 2. By radio labeling given in Definition 3, a graph GV,E is a one-to-one function f:V⟶0,∞ such that, for every u,v∈V, fu−fv≥1+diamG−du,v. We have the following cases.Case (a): letdu,v=2. If diamGSZn=2 and du,v=2, then, by the function of radio labeling f, we have fu−fv≥1+2−2. Clearly, fvi−fvj≥1.Case (b): letdu,v=1. If diamGSZn=2 and du,v=1, then we have fu−fv≥1+2−1. Clearly, fvi−fvj≥2.By the above cases, one can easily conclude that radio labeling is the same asLh,k-labeling when h=2 and k=1.Clearly, the proof of the Theorems in Section3 is directly applicable to the radio labeling. Hence, GSZn admits radio labeling with minimum index.


## 5. Conclusion and Further Research Work

In this paper, we have worked onLh,k labeling of a new family of graphs, i.e., an inverse graph with a finite cyclic group. We provided the upper bounds of the index for five specific cases, that is, n≥3 is an odd integer; then, λkhGSZn≤n−1/2h+k;n is even integer with k≥⌈h/2⌉ and n≡2mod4, then λkhGSZn≤n−2/4h+3k+k;n is even integer with k≥⌈h/2⌉ and n≡0mod4, then λkhGSZn≤n/4h+3k−k; n is even integer with k<⌈h/2⌉ and n≡2mod4, then λkhGSZn≤n−2/2h+n+2/4k;n is even integer with k<⌈h/2⌉ and n≡0mod4, then λkhGSZn≤n/2−1h+n+4/4k. We have generalized the results and obtained the bounds for Lh,k labeling of inverse graph of a finite cyclic group of order n. The novelty of this research is bounds of the index which are sharp and the results are directly applicable to the radio labeling minimum index. However, the problem remains open to find Lh,k-labeling with the minimum index for the inverse graphs of dihedral and symmetric groups in general. Furthermore, research is inspired to notice the Lh,k labeling of the inverse graph for an arbitrary finite group.



---

*Source: 5583433-2021-03-26.xml*