# Modular Irregular Labeling on Double-Star and Friendship Graphs

Authors: K. A. Sugeng; Z. Z. Barack; N. Hinding; R. Simanjuntak
Journal: Journal of Mathematics
 (2021)

---

## Abstract

A modular irregular graph is a graph that admits a modular irregular labeling. A modular irregular labeling of a graphG of order n is a mapping of the set of edges of the graph to 1,2,…,k such that the weights of all vertices are different. The vertex weight is the sum of its incident edge labels, and all vertex weights are calculated with the sum modulo n. The modular irregularity strength is the minimum largest edge label such that a modular irregular labeling can be done. In this paper, we construct a modular irregular labeling of two classes of graphs that are biregular; in this case, the regular double-star graph and friendship graph classes are chosen. Since the modular irregularity strength of the friendship graph also holds the minimal irregularity strength, then the labeling is also an irregular labeling with the same strength as the modular case.


---

## Body

## 1. Introduction

Graph labeling is a mapping of a set of numbers, called the labels, to the graph elements, usually vertices or edges [1]. Generally, the label is a positive integer. There are several labelings that have been developed; among them are irregular labeling and modular irregular labeling. The reader can check the dynamic survey of graph labeling by Gallian to obtain more information on various labeling [1]. In 1988, irregular labeling was first introduced by Chartrand et al. [2]. To date, there have been studies on the irregular labelings of certain graphs. The terminology not included in this paper can be found in [3].An irregular labeling is defined as a labelingf:E⟶1,2,…,k with k as a positive integer, such that wtfx=∑y∈Nxfxy is different for all vertices, where Nx is a neighbour of vertex x. The irregularity strength sG of a graph G is the minimum value of k for which G has irregular labeling with labels at most k. The irregularity strength sG of a graph G is defined only for graphs containing at most one isolated vertex and no connected component of order 2. The lower bound of the irregularity strength of a graph G is sG≥max1≤i≤△ni+i−1/i, where ni vertices with degree i, as stated in Theorem 1. For a regular graph G, Przyboylo [4] has proved an upper bound of an irregularity strength is sG<16n/d+6. For tree graphs, Aigner and Triesch [5] proved that the irregularity strength of any tree with no vertices of degree two is equal to the number of its leaves. Ferrara et al. [6] later proved that if the tree T has every two vertices of degree not equal to two at a distance of at least eight with number of leaves at least three, then sT=n1+n2/2, where n1 is the number of leaves and n2 is the number of vertices of degree two. The survey of irregular labeling has been done by Bača et al. [7]. After this survey paper, there are still many results which have been found. See Gallian’s survey, for the update [1].Modular irregular labeling of a graph is a mappingφ:EG⟶1,2,…,k so that a bijective function wtφx=∑y∈Nxφxy can be defined and has different values. The set of the weights of the vertices is a group of integers modulo n. The minimum k such that this kind of labeling exists is called the modular irregularity strength of G and denoted by msG. Bača et al. [8] determined the modular irregularity strength of path, star, triangular graph, cycle, and gear graphs. Muthugurupackiam et al. [9] proved the modular irregularity of the tadpole graph and double-cycle graph. Later, Bača et al. [10] proved the modular irregularity strength of the fan graph. In this paper, we construct the modular irregular labeling and determine its modular irregularity strength of regular double-star graph and friendship graph.


## 2. Known Results

There are some known results that we will use to prove the modular irregularity strength of the star and friendship graphs that we gave in this section. A lower bound on the irregularity strength is already known by Chartrand et al. as stated in the following theorem.Theorem 1 (see [2]).
LetGbe a connected graph with an ordermore than2, which hasnivertices with degreei. Then,(1)sG≥max1≤i≤ΔGni−1i+1.The relation between the irregularity strength and modular irregularity strength has been known and presented in the following theorem.Theorem 2 (see [8]).
LetGbe a graph without a component of order≤2. Then,(2)sG≤msG,
Not all graphs can have modular irregular labeling. In the following theorem, Bača et al. give a requirement of a graph that cannot have a modular irregular labeling, denoted bymsG=∞.Theorem 3 (see [8]).
IfGis a graph of ordern,n≡2mod4, thenGhas no modular irregulark-labeling, i.e.,msG=∞.


## 3. New Results

This section gives two results on a modular irregular labeling on a regular double-star graph and a friendship graph. Aman and Togni [5] and Ferrara et al. [6] proved the irregularity strength of trees family. The modular irregularity strength of the family of trees which is already known is path and star [8]. Since we consider biregular graphs in this paper, then the regular trees family that we choose is regular double-stars.A regular double-star graphSk,k is a graph built from two copies of a star graph Sk, and then, we connect the two center vertices of the star. Note that a star Sk has k+1 vertices. Thus, Sk,k has 2k+2 vertices and 2k+1 edges.Theorem 4.
LetSk,k,k≥1be a regular double-star graph. Then,(3)msSk,k=2k,kis odd.∞,kis even.Proof.
Letx and y be the two centers of the double-star graph. Let xi,i=1,…,k, be the leaves of the center vertex x and yi,i=1,…,k, be the leaves of the center vertex y.
Fork even, VSk,k=2k+2≡2mod4. Then, following Theorem 3, the graph does not have a modular irregular labeling.
Fork odd, label the edges as follows.
For1≤i≤k,(4)φxxi=2i−1,iodd,2i,ieven,φyyi=2i,iodd,2i−1,ieven,(5)φxy=3k+12<2k.
The pendant leaves should have the different labels; then, the minimal number of labels is2k. The maximal label is at φyyk=2k. Thus, φ is a 2k-labeling. Its leaves weight will be elements of 1,2,…,2k, wtφx≡2k+1mod2k+2 and wtφy≡0mod2k+2. All vertex weights are different. Thus,msSk,k=2k for k odd.
A friendship graphFn is a graph with the vertex set m,x1,...,xn,y1,...,yn and the edge set is mx1,…,mxn,my1,…myn,x1y1,…,xnyn. Thus, the graph Fn has 2n+1 vertices and 3n edges. Since the graph has VG≠2mod4, then based on Theorem 3, we have a possibility to find the modular irregularity strength of Fn. In the following lemma, we have a lower bound of msFn.Lemma 1.
LetFnbe a friendship graph withn≥2. Then,(6)msFn≥n+1.Proof.
A friendship graphFn has 2n vertices with degree two and one vertex with degree 2n. Based on Theorem 1, we have(7)sFn≥max1≤i≤2n2n−12+1,1−12n+1,sFn≥n+12,sFn≥n+1sincesFnis an integer.
Then, based on Theorem2, we obtain(8)msFn≥sFn≥n+1.msFn≥n+1.
A modular irregular labeling can be constructed andmsFn can be determined, and the conclusion is written in the following theorem.Theorem 5.
LetFnbe a friendship graph withn≥2. Then, msFn=n+1.Proof.
We divide the proof in 4 cases. In each case, we define the edge labelingφ:EG⟶1,2,…,3n and show that ϕ is an n+1-labeling. Then, in the second step, we show that the vertex weights are all different.


### 3.1. Casen≡0mod4

Label the edges as follows.(9)φxiyi=2,i=1,i+2,i=2,3,…,n2andi>n2,iodd,i+1,i>n2,ieven,φxim=1,i=1,i−1,i=2,3,…,n2andi>n2,iodd,i,i>n2,ieven,φyim=2,i=1,i,i=2,3,…,n2andi>n2,iodd,i+1,i>n2,ieven.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we can obtain maxφxiyi,φxim,φyim:1≤i≤n=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling.(b)
The edges adjacent toxi are xiyi and xim so that for i=1(10)wtφx1=φx1y1+φx1m=2+1=3,fori=2,3,…,n/2andi>n/2,iodd,(11)wtφxi=φxiyi+φxim=2i+1,fori>n/2,ieven,(12)wtφxi=φxiyi+φxim=2i+1.Thus, we have the vertex weight,wtφxi=2i+1,i=1,2,…,n.(c)
The edges adjacent toyi is xiyi and yim so that for i=1,(13)wtφy1=φx1y1+φy1m=2+2=4.Fori=2,3,…,n/2andi>n/2,iodd,(14)wtφyi=φxiyi+φyim=i+2+i=2i+2.Fori>n/2,ieven,(15)wtφyi=φxiyi+φyim=i+1+i+1=2i+2.Thus, we have the vertex weight,wtφyi=2i+2,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(16)wtφm=∑i=1nφxim+φyim=1+∑i=2n2i−1+∑i=1n4n2+2i−1−1+∑i=1n4n2+2i+2+∑i=2n2i+∑i=1n4n2+2i−1+∑i=1n4n2+2i+1=n2+n2+2=2n+1n2+2≡2mod2n+1.


### 3.2. Casen≡1mod4,n>1

Label the edges as follows.(17)φxiyi=i+1,i=1,2,…,n+32andi>n+32,iodd.i+2,i>n+32,ieven.φxim=i,i=1,2,…,n+32andi>n+32,iodd.i−1,i>n+32,ieven.φyim=i+1,i=1,2,…,n+32andi>n+32,iodd.i,i>n+32,ieven.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we can have max{φxiyi),φ(xim,φyim:1≤i≤n}=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling for the graph Fn.(b)
The edges adjacent toxi is xiyi and xim so that, for i=1,2,…,n+3/2andi>n+3/2,iodd,(18)wtφxi=φxiyi+φxim=i+1+i=2i+1.Fori>n+3/2,ieven,(19)wtφxi=φxiyi+φxim=i+2+i−1=2i+1.Then, we have the vertex weight,wtφxi=2i+1,i=1,2,…,n.(c)
The edges adjacent toyi are xiyi and yim so that, for i=1,2,…,n+3/2andi>n+3/2,iodd,(20)wtφyi=φxiyi+φyim=i+1+i+1=2i+2.Fori>n+3/2,ieven,(21)wtφyi=φxiyi+φyim=i+2+i=2i+2.Then, we obtain the vertex weightwtφyi=2i+2,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(22)wtφm=∑i=1nφxim+φyim=∑i=1n+32i+∑i=1n−14n+32+2i−1+∑i=1n−54n+32+2i−1+∑i=1n+32i+1+∑i=1n−14n+32+2i−1+1+∑i=1n−54n+32+2i=2n+1n+12+2≡2mod2n+1.


### 3.3. Casen≡2mod4

Label the edges as follows:(23)φxiyi=i,i=1,2,…,n2,i+1i>n2,ieven,i+2i>n2,iodd,φxim=i,i=1,2,…,n2,i−1i>n2,ieven,i−2i>n2,iodd.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we have max{φxiyi),φ(xim,φyim:1≤i≤n}=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling for the graph Fn.(b)
The edges adjacent toxi are xiyi and xim so that, for i=1,2,…,n/2,(24)wtφxi=φxiyi+φxim=i+i=2i.Fori>n/2,ieven,(25)wtφxi=φxiyi+φxim=i+1+i−1=2i.Fori>n/2,iodd,(26)wtφxi=φxiyi+φxim=i+2+i−2=2i.Then, we obtain the vertex weightwtφxi=2i,i=1,2,…,n.(c)
The edges adjacent toyi are xiyi and yim so that, for i=1,2,…,n/2,(27)wtφyi=φxiyi+φyim=i+i+1=2i+1.Fori>n/2,ieven,(28)wtφyi=φxiyi+φyim=i+1+i=2i+1.Fori>n/2,iodd,(29)wtφyi=φxiyi+φyim=i+2+i−1=2i+1.Then, we conclude that the vertex weightwtφyi=2i+1,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(30)wtφm=∑i=1nφxim+φyim=∑i=1n2i+∑i=1n+24n2+2i−1−1+∑i=1n−24n2+2i−2+∑i=1n2i+1+∑i=1n+24n2+2i−1+∑i=1n−24n2+2i−1wtφm=2n+1n2+1≡1mod2n+1.


### 3.4. Casen≡3mod4,n>3

Label the edges as follows:(31)φxiyi=i,i=1,2,…,n+32andi>n+32,ieven,i+1,i>n+32,iodd,φxim=i,i=1,2,…,n+32andi>n+32,ieven,i−1,i>n+32,iodd,φyim=i+1,i=1,2,…,n+32andi>n+32,ieven,i,i>n+32,iodd.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we have max{φxiyi),φ(xim,φyim:1≤i≤n}=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling for the graph Fn.(b)
The edges adjacent toxi are xiyi and xim so that, for i=1,2,…,n+3/2andi>n+3/2,ieven,(32)wtφxi=φxiyi+φxim=i+i=2i.Fori>n+3/2,iodd,(33)wtφxi=φxiyi+φxim=i+1+i−1=2i.Then, we have the vertex weightwtφxi=2i,i=1,2,…,n.(c)
The edges adjacent toyi are xiyi and yim so that, for i=1,2,…,n+3/2andi>n+3/2,ieven,(34)wtφyi=φxiyi+φyim=i+i+1=2i+1.Fori>n+3/2,iodd,(35)wtφyi=φxiyi+φyim=i+1+i=2i+1.Then, we can conclude that the vertex weightwtφyi=2i+1,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(36)wtφm=∑i=1nφxim+φyim∑i=1n+32i+∑i=1n−34n+32+2i−1+∑i=1n−34n+32+2i−1+∑i=1n+32i+1+∑i=1n−34n+32+2i−1+1+∑i=1n−34n+32+2iwtφm=2n+1n+12+1≡1mod2k2n+1.In all cases, we proved that the vertex weights are all different and the maximum label isn+1. By combining the results msFn≤n+1 and Lemma 1 (ms(Fn)≥n+1), we conclude that msFn=n+1, for n≥2.From Theorem5, we have msFn=n+1 is equal to the lower bound of the irregularity strength from Theorem 1. We can conclude that the friendship graph has irregular labeling with sFn=n+1.Corollary 1.
The friendship graphFnhas the irregularity strengthsFn=n+1forn≥2.


## 3.1. Casen≡0mod4

Label the edges as follows.(9)φxiyi=2,i=1,i+2,i=2,3,…,n2andi>n2,iodd,i+1,i>n2,ieven,φxim=1,i=1,i−1,i=2,3,…,n2andi>n2,iodd,i,i>n2,ieven,φyim=2,i=1,i,i=2,3,…,n2andi>n2,iodd,i+1,i>n2,ieven.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we can obtain maxφxiyi,φxim,φyim:1≤i≤n=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling.(b)
The edges adjacent toxi are xiyi and xim so that for i=1(10)wtφx1=φx1y1+φx1m=2+1=3,fori=2,3,…,n/2andi>n/2,iodd,(11)wtφxi=φxiyi+φxim=2i+1,fori>n/2,ieven,(12)wtφxi=φxiyi+φxim=2i+1.Thus, we have the vertex weight,wtφxi=2i+1,i=1,2,…,n.(c)
The edges adjacent toyi is xiyi and yim so that for i=1,(13)wtφy1=φx1y1+φy1m=2+2=4.Fori=2,3,…,n/2andi>n/2,iodd,(14)wtφyi=φxiyi+φyim=i+2+i=2i+2.Fori>n/2,ieven,(15)wtφyi=φxiyi+φyim=i+1+i+1=2i+2.Thus, we have the vertex weight,wtφyi=2i+2,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(16)wtφm=∑i=1nφxim+φyim=1+∑i=2n2i−1+∑i=1n4n2+2i−1−1+∑i=1n4n2+2i+2+∑i=2n2i+∑i=1n4n2+2i−1+∑i=1n4n2+2i+1=n2+n2+2=2n+1n2+2≡2mod2n+1.


## 3.2. Casen≡1mod4,n>1

Label the edges as follows.(17)φxiyi=i+1,i=1,2,…,n+32andi>n+32,iodd.i+2,i>n+32,ieven.φxim=i,i=1,2,…,n+32andi>n+32,iodd.i−1,i>n+32,ieven.φyim=i+1,i=1,2,…,n+32andi>n+32,iodd.i,i>n+32,ieven.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we can have max{φxiyi),φ(xim,φyim:1≤i≤n}=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling for the graph Fn.(b)
The edges adjacent toxi is xiyi and xim so that, for i=1,2,…,n+3/2andi>n+3/2,iodd,(18)wtφxi=φxiyi+φxim=i+1+i=2i+1.Fori>n+3/2,ieven,(19)wtφxi=φxiyi+φxim=i+2+i−1=2i+1.Then, we have the vertex weight,wtφxi=2i+1,i=1,2,…,n.(c)
The edges adjacent toyi are xiyi and yim so that, for i=1,2,…,n+3/2andi>n+3/2,iodd,(20)wtφyi=φxiyi+φyim=i+1+i+1=2i+2.Fori>n+3/2,ieven,(21)wtφyi=φxiyi+φyim=i+2+i=2i+2.Then, we obtain the vertex weightwtφyi=2i+2,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(22)wtφm=∑i=1nφxim+φyim=∑i=1n+32i+∑i=1n−14n+32+2i−1+∑i=1n−54n+32+2i−1+∑i=1n+32i+1+∑i=1n−14n+32+2i−1+1+∑i=1n−54n+32+2i=2n+1n+12+2≡2mod2n+1.


## 3.3. Casen≡2mod4

Label the edges as follows:(23)φxiyi=i,i=1,2,…,n2,i+1i>n2,ieven,i+2i>n2,iodd,φxim=i,i=1,2,…,n2,i−1i>n2,ieven,i−2i>n2,iodd.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we have max{φxiyi),φ(xim,φyim:1≤i≤n}=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling for the graph Fn.(b)
The edges adjacent toxi are xiyi and xim so that, for i=1,2,…,n/2,(24)wtφxi=φxiyi+φxim=i+i=2i.Fori>n/2,ieven,(25)wtφxi=φxiyi+φxim=i+1+i−1=2i.Fori>n/2,iodd,(26)wtφxi=φxiyi+φxim=i+2+i−2=2i.Then, we obtain the vertex weightwtφxi=2i,i=1,2,…,n.(c)
The edges adjacent toyi are xiyi and yim so that, for i=1,2,…,n/2,(27)wtφyi=φxiyi+φyim=i+i+1=2i+1.Fori>n/2,ieven,(28)wtφyi=φxiyi+φyim=i+1+i=2i+1.Fori>n/2,iodd,(29)wtφyi=φxiyi+φyim=i+2+i−1=2i+1.Then, we conclude that the vertex weightwtφyi=2i+1,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(30)wtφm=∑i=1nφxim+φyim=∑i=1n2i+∑i=1n+24n2+2i−1−1+∑i=1n−24n2+2i−2+∑i=1n2i+1+∑i=1n+24n2+2i−1+∑i=1n−24n2+2i−1wtφm=2n+1n2+1≡1mod2n+1.


## 3.4. Casen≡3mod4,n>3

Label the edges as follows:(31)φxiyi=i,i=1,2,…,n+32andi>n+32,ieven,i+1,i>n+32,iodd,φxim=i,i=1,2,…,n+32andi>n+32,ieven,i−1,i>n+32,iodd,φyim=i+1,i=1,2,…,n+32andi>n+32,ieven,i,i>n+32,iodd.(a)
Letφ be an edge labeling of the friendship graph Fn that is defined above; we have max{φxiyi),φ(xim,φyim:1≤i≤n}=n+1.Then, it is proved that the edge labelingφ is an n+1-labeling for the graph Fn.(b)
The edges adjacent toxi are xiyi and xim so that, for i=1,2,…,n+3/2andi>n+3/2,ieven,(32)wtφxi=φxiyi+φxim=i+i=2i.Fori>n+3/2,iodd,(33)wtφxi=φxiyi+φxim=i+1+i−1=2i.Then, we have the vertex weightwtφxi=2i,i=1,2,…,n.(c)
The edges adjacent toyi are xiyi and yim so that, for i=1,2,…,n+3/2andi>n+3/2,ieven,(34)wtφyi=φxiyi+φyim=i+i+1=2i+1.Fori>n+3/2,iodd,(35)wtφyi=φxiyi+φyim=i+1+i=2i+1.Then, we can conclude that the vertex weightwtφyi=2i+1,i=1,2,…,n.(d)
The edges adjacent tom are xim and yim so that(36)wtφm=∑i=1nφxim+φyim∑i=1n+32i+∑i=1n−34n+32+2i−1+∑i=1n−34n+32+2i−1+∑i=1n+32i+1+∑i=1n−34n+32+2i−1+1+∑i=1n−34n+32+2iwtφm=2n+1n+12+1≡1mod2k2n+1.In all cases, we proved that the vertex weights are all different and the maximum label isn+1. By combining the results msFn≤n+1 and Lemma 1 (ms(Fn)≥n+1), we conclude that msFn=n+1, for n≥2.From Theorem5, we have msFn=n+1 is equal to the lower bound of the irregularity strength from Theorem 1. We can conclude that the friendship graph has irregular labeling with sFn=n+1.Corollary 1.
The friendship graphFnhas the irregularity strengthsFn=n+1forn≥2.


## 4. Conclusion

In this paper, we prove the modular irregularity strength of two graphs, which are the regular double-star graphSk,k, that has msSk,k=2k, for k≥1 and k is odd and for the friendship graph Fn that has msFn=n+1 and sFn=n+1, for n≥2. There are still many families of graphs that can be explored to determine its modular irregularity strength.



---

*Source: 4746609-2021-12-28.xml*