# On Valuation of Edge Irregularity Strength of Certain Graphical Families

Authors: Zhiqiang Zhang; Tariq Mehmood; Atiq ur Rehman; Muhammad Hussain; Xiujun Zhang
Journal: Journal of Mathematics
 (2022)

---

## Abstract

This article comprises of exact valuation of a graph parameter, known as the edge irregularity strengthEIS, symbolized as eisG, of various graphical families such as middle graph of path graph, middle graph of cycle graph, snake graph (string 2), paramedian ladder, and complete m-partite graphs. If δ:V⟶1,2,…,p is a function defined on vertices of a graph that helps to determine different weights for every pair of edges, the least value of p is the target. Thus, addition operation for allocated to vertices of an edge, i.e., δvi+δvj, i≠j=1,2,…,n, defines the weight wδvivj of corresponding edge for every vivj∈E. If two different edges ei and ej in graph G carry weights in different manner, i.e., wδei≠wδei for i≠j. Then the edge irregular p-labeling is defined after a vertex p-labeling of G. After establishing various novel results and making some conclusions, an open problem is mentioned in the end.


---

## Body

## 1. Introduction

In the modern era, several researchers have shown interest in graph labeling, and so many label findings emerge every year. Such success is attributed not just to the technical complexities of graph labeling but also to the diverse range of applications such as electron microscopy,X-ray, combinatorial optimization, sonar, physics, signal conditioning, network programming, and system layout.Undirected, simple, and finite graphs are being considered in this article, for instance, a graph structureG=V,E with pair of sets V (vertices) and E (edges/nodes). Then a mapping that assigns non-negative values to some graph elements is referred to as labeling of G. If a mapping uses all vertices as well as edges of G, then it is known as total labeling. While for a domain containing V or E only, then the associated labeling is vertex-labeling or edge-labeling in a respective manner. Therefore, in order to have an edge p-labeling, δ:E⟶1,2,…,p, the corresponding vertex v∈V carries a weight equal to the labels sum of edges vvi, i=1,2,…,n, where vi are the adjacent vertices to v i.e., wδv=∑δvvi. Other domains are possible, harmonious, cordial, graceful, magic and super magic are examples of graph labeling.Baca and Siddiqui [1] defined the edge p-labeling θ from E to 1,2,…,p such that wθx≠wθy for all x≠y∈V of a graph G. The least value p is the irregularity strength, and the highest label of graph G. This variable has attracted much attention of researchers [2–8].In 2012, Nurdin [9] considered the banana and quad trees in order to determine their total vertex irregularity strength TVIS. Furthermore, Ahmad et al. [4] took the disjoint union of Halm graph and evaluated the TVIS. Some results relating to graph labeling can be found in [1, 6, 10–13].Al-Mushayt et al. [6] evaluated the total vertex inconsistency quality (irregularity strength) of a graph named convex polytope in 2013. A mapping α:V⟶1,2,…,m is said to be edge irregular m-labeling of G if for all ab,cd∈E there exist wαab≠wαcd, where the wαab=αa+αb and wαcd=αc+αd. The minimal m among upper bound of range set for which the graph G has an edge irregular m-labeling is said to be edge strength of G denoted by eisG. In 2014, Ahmed et al. [14] evaluated the bounds for eisG and decided careful estimation of eisG for paths, stars, twofold stars, and Cartesian result of two paths.In this paper, we aim to label the graphs in an irregular manner and a few families in the relation of graphs, namely, middle graph of path graph, middle graph of cycle graph, snake graph (string 2), and paramedian ladder, and completem-partite graphs are considered to estimate their irregularity strengths.Following are some important results developed in literature of graph theory [14].


### 1.1. Theorem A

For any simple graphG whose degree Δ=ΔG as largest, then eisG≥ max ⌈E+1/2⌉,ΔG.


### 1.2. Theorem B

ForPn be a path on n≥2 vertices, eisPn=⌈n/2⌉.


### 1.3. Theorem C

Forn≥1,K1,n be a star on n+1 vertices, eisK1,n=n.


### 1.4. Theorem D

ForSm,n be twofold star with 3≤m≤n, eisSm,n=n.


### 1.5. Theorem E

Edge inconsistency quality of Cartesian product of two pathsGn and Gm is ⌈2mn−m−n+1/2⌉ with m,n≥2.


### 1.6. Theorem F

k is the order of graph. Nm is the sequence of Fibonacci numbers obtained by the narration Np=Np−1+Np−2 with p≥3 with initial values N1=1 and N2=2. Then eis of graph is less than or equal to Np.


## 1.1. Theorem A

For any simple graphG whose degree Δ=ΔG as largest, then eisG≥ max ⌈E+1/2⌉,ΔG.


## 1.2. Theorem B

ForPn be a path on n≥2 vertices, eisPn=⌈n/2⌉.


## 1.3. Theorem C

Forn≥1,K1,n be a star on n+1 vertices, eisK1,n=n.


## 1.4. Theorem D

ForSm,n be twofold star with 3≤m≤n, eisSm,n=n.


## 1.5. Theorem E

Edge inconsistency quality of Cartesian product of two pathsGn and Gm is ⌈2mn−m−n+1/2⌉ with m,n≥2.


## 1.6. Theorem F

k is the order of graph. Nm is the sequence of Fibonacci numbers obtained by the narration Np=Np−1+Np−2 with p≥3 with initial values N1=1 and N2=2. Then eis of graph is less than or equal to Np.


## 2. Main Results

This section defines the middle graph of the path and the cycle graphs. Irregular labeling will be formulated and a lower bound of irregularity for different graphs will be found.


### 2.1. Middle Graph of Path Graph

Ifk vertices ai:1≤i≤k carry a path Pk, and bi:1≤i≤k−1 is another set of vertices. Then the graph MPk is said to be middle graph of path graph including the sets of vertices and edges, respectively, given as follows:(1)VMPk=ai:1≤i≤k∪bi:1≤i≤k−1,eMPk=aiai+1:1≤i≤k−1∪aibi:1≤i≤k−1∪biai+1:1≤i≤k−1.


### 2.2. Middle Graph of Cycle Graph

IfCk is cycle of k vertices xj:1≤j≤k and yj:1≤j≤k is another set of vertices. Then the graph MCk is said to be middle graph of cycle graph including the sets of vertices and edges, respectively, given as follows:(2)VMCk=xj:1≤j≤k∪yj:1≤j≤k,eMCk=xjxj+1:1≤j≤k−1∪xkx1∪xjyj:1≤j≤k∪yjxj+1:1≤j≤k−1∪ykx1.


### 2.3. Ceiling Function

We define ceiling function asy=⌈fx⌉, when image of any value is in fraction like 5/2, we take this value as 3.Theorem 1.
LetMPq is middle graph of the path graph Pq with q≥2. Then eisMPq=2q−1.Proof.
ConsiderPq be path graph of q vertices, MPq is middle graph of the path graph including the following sets, vMPq and eMPq, of vertices and edges, respectively, given as follows:(3)vMPq=um:1≤m≤q∪vn:1≤n≤q−1,eMPq=uiui+1:1≤i≤q−1∪ujvj:1≤j≤q−1∪vkuk+1:1≤k≤q−1.
Order of graphMPq is 2q−1 and size is 3q−1. Presently, we characterize a mapping α:V⟶1,2,3,…,2q−1 as follows:(4)αui=2i−1,1≤i≤q,αvj=2j,1≤j≤q−1.
Degree of eachui2≤i≤q−1 is 4 and degree of u1, uq, and vj1≤j≤q−1 is 2. No two vertices have same labels for irregular labeling. The label of vertex uq is 2q−1 which is edge strength of MPq. Weights of edges are given as follows:(5)wαuiui+1=αui+αui+1=4i,1≤i≤q−1,wαujvj=αuj+αvj=4j−1,1≤j≤q−1,wαvkvk+1=αvk+αvk+1=4k+1,1≤k≤q−1.
Edge weights are distinct for all distinct edges, i.e., for any two edgese and fwαe≠wαf. Thus apex (vertex) labeling is an edge irregular 2q−1 labeling. Hence, we have eisMPq=2q−1.Example 1.
The diagram in Figure1 is the example of irregular labeling of MQ6 that carries eisMQ6=11.Figure 1
Irregular labeling ofMQ6 with eisMQ6=11.Theorem 2.
LetCr,r≥2 is Cycle graph, MCr is middle graph of cycle graph. Then(6)eisMCr=2r−1for risodd2r+1for riseven.Proof.
LetCr be a cycle graph of r vertices and MCr is middle graph including VMCr and EMCr as vertex set and edge set, respectively, given as follows:(7)VMCr=pl:1≤l≤r∪qm:1≤m≤r,EMCr=piqi+1:1≤i≤r−1∪pjqj:1≤j≤r∪qkpk+1:1≤k≤r−1∪qrp1∪prp1.
The order ofMCr is 2r and size is 3r, while the degree of each pi is 4 and the degree of each qi is 2 and no two vertices have same labels for irregular labeling. In this graph there are two possible cases.Case-i: whenr is odd we define function β:VMCr⟶1,2,3,…,2r−1 as follows:(8)βpi=2i−1,1≤i≤r,βqj=2j,1≤j≤r−1,βqr=5.Weights of edges are as follows:(9)wβpipi+1=βpi+βpi+1=4i,1≤i≤r−1,wβprp1=βpr+βp1=2r,wβpjqj=βpj+βqj=4j−1,≤k≤r−1,wβqkpk+1=βqk+βpk+1=4k+1,1≤k≤r−1,wβprq1=βpr+βq1=6,wβprqn=βpr+βqn=2r+4.Here distinct edges carry distinct weights, i.e., for any two edgese and fwβe≠wβf. Last vertex pr of Cr has label 2r−1. Thus, vertex labeling β is an edge irregular 2r−1 labeling. Hence eisG=2r−1.Case-ii: for evenr we define transformation β:VMCr⟶1,2,3,…,2r+1 as follows:(10)βpi=2i−1,1≤i≤r−1,βpr=2r+1,βqj=2j,1≤j≤r−1,βqr=5.
Weights of edges in this case are given as follows:(11)wβpipi+1=βpi+βpi+1=4i,1≤i≤r−2,wβpn−1pn=βpn−1+βpn=4n+2,wβpjqj=βpj+βqj=4j−1,1≤j≤r−2,wβpnqn=βpn+βqn=2n+6,wβqkpk+1=βqk+βpk+1=4k+1,1≤k≤r−1,wβpnq1=βpn+βq1=6.
Here the edge weights are distinct for all pairs of distinct edges i.e., for any two edgese and fwβe≠wβf, and last vertex pr of Cr has label 2r+1. Therefore, labeling is an edge irregular 2r+1 labeling. Hence, we have eisG=2r+1.Example 2.
The diagram in Figure2 is the example of irregular labeling of MC10 that carries eisMC10=21.Figure 2
Irregular labeling ofMC10 with eisMC10=21.Theorem 3.
Pm1 is path with m1 vertices and K2,n1 is complete bipartite graph. Graph G=K2,n1ΔPm1 is paramedian ladder graph. Then(12)eisG=2m1n1+1−12.Proof.
letE2G and V2G are the edge and vertex sets, respectively, of the graph G.(13)V2G=uij:1≤i≤n1,1≤j≤m1∪vk:1≤k≤2m1,E2G=uijvk:1≤i≤n1,1≤j≤m1,1≤k≤2m1∪u1ju1j+1:1≤j≤m1−1∪un1jun1j+1:1≤j≤m1−1.
The order ofG is m1n1+2 and size is 2m1n1+1−2. From Theorem A, eisG≥max⌈2m1n1+2m1−1/2⌉,ΔG. ΔG represents degree of the graph. Since degree of G is n1 so eisG≥⌈2m1n1+2m1−1/2⌉. To show equality it suffices to prove existence of an edge irregular ⌈2m1n1+2m1−1/2⌉ labeling. For this we define mapping ϕ:V⟶1,2,3,…,2m1n1+2m1−1/2 as follows:(14)ϕui2j−1=2n1+1j−1+i,1≤i≤n1,1≤j≤m1,ϕun1−12j=2jn1+1−n1,1≤j≤m1,ϕun12j=2jn1+1−n1+1,1≤j≤m1′ϕun1−i2j=2jn1+1−n1+i,1≤j≤m1,2≤i≤n1−1,ϕv2i=in1+1,1≤i≤n1,ϕv2i−1=in1+1−n1,1≤i≤n1.
Weights of edges are given as follows:(15)wϕv2k−1ui2j−1=ϕv2k−1+ϕui2j−1=2j−1+kn1+1+i−n1,1≤i≤n1,1≤j≤m1,k≅1mod2,wϕv2k−1un1−12j=ϕv2k−1+ϕun1−12j=2j+kn1+1−2n1,1≤j≤m1,k≅0mod2,wϕv2k−1un12j=ϕv2k−1+ϕun12j=2j+kn1+1−2n1+1,2≤i≤n1−1,1≤j≤m1,k≅0mod2,wϕv2k−1un1−i2j=ϕv2k−1+ϕun1−i2j=2j+kn1+1−2n1+i,2≤i≤n1−1,1≤j≤m1,k≅0mod2,wϕv2kui2j−1=ϕv2k+ϕui2j−1=2j−1+kn1+1+i,1≤i≤n1,1≤j≤m1,k≅1mod2,wϕv2kun1−12j=ϕv2k+ϕun1−12j=2j+kn1+1−n1,1≤j≤m1,k≅0mod2,wϕv2kun12j=ϕv2k+ϕun12j=2j+kn1+1−n1+1,1≤j≤m1,k≅0mod2,wϕv2kun1−i2j=ϕv2k+ϕun1−i2j=2j+kn1+1−n1+i,2≤i≤n1−1,1≤j≤m1,k≅0mod2.
Weights form (2,1) irregular labeling. For any two different edges, their loads are different. Thus vertex labeling is an edge irregular⌈2m1n1+1−1/2⌉ labeling. Hence, we get eisG=⌈2m1n1+1−1/2⌉.Example 3.
The diagram in Figure3 is the example of irregular labeling of G=K2,6△P4 that carries eisG=28.Figure 3
Irregular labeling ofG=K2,6△P4 with eisG=28.Theorem 4.
Theorem 4.LetGV,E be a snake graph of n-rectangles with string 2,2,…,2. Then eisG=⌈4n+1/2⌉.Proof.
Let snake graphG with n-rectangles includes following sets V and E of vertices and edges, respectively,(16)V=ui:1≤i≤n+1∪vj:1≤j≤n∪wk:1≤k≤n,E∪wlul+1:1≤l≤n.
The order ofG is 3n+1 and size is 4n. From Theorem A, eisG≥max⌈4n+1/2⌉, ΔG. Since max degree of G is 4 so eisG≥⌈4n+1/2⌉. To show equality, it suffices to prove existence of an edge irregular ⌈4n+1/2⌉ labeling. For this we define mapping γ:V⟶1,2,3,…,4n+1/2 as follows:(17)γvi=2i−1,1≤i≤n,γuj=2j−1,1≤j≤n+1,γwk=2k,1≤k≤n.
Last vertexun+1 of G has label ⌈4n+1/2⌉. Furthermore, the weights of edges are given by(18)wγuivi=γui+γvi=4i−2,1≤i≤n,wγvjuj+1=γvj+γuj+1=4j,1≤i≤n,wγukwk=γuk+γwk=4k−1,1≤k≤n,wγwlul+1=γwl+γul+1=4l+1,1≤l≤n.
Edge weights are distinct for all pairs of distinct edges i.e., for any two edgese and fwγe≠wγf. Thus, vertex labeling is an edge irregular ⌈4n+1/2⌉ labeling. Hence, we have eisG=⌈4n+1/2⌉.Example 4.
The diagram in Figure4 is the example of irregular labeling of a snake graph G of 5-strings and carries eisG=11.Figure 4
Irregular labeling of a snake graphG of 5-strings with eisG=11.Theorem 5.
LetTm,n be a m-partite complete graph with m set of vertices and each set contains n vertices. Then for m = 3, eisT3,n=nn2+2.Proof.
letVT3,n and ET3,n denote the vertex set and edge set of T3,n, respectively,(19)VT3,n=xi:1≤i≤n∪yj:1≤j≤n∪zk:1≤k≤n,ET3,n=xiyj:1≤i≤n,1≤j≤n∪xizk:1≤i≤n,1≤k≤n∪yjzk:1≤j≤n,1≤k≤n.
The order of the graphT3,n is 3n and size is 3n2. Since eisG≥max⌈E+1/2⌉,ΔG. Max degree of G is n. Now we define function ϕ:V⟶1,2,…,nn2+2 such that(20)ϕxi=i,1≤i≤n,ϕy1=n+1,ϕyj+1=n+1+jn,1≤j≤n−1,ϕz1=n2+n+1,ϕzk+1=k+1n2+1+n,1≤k≤n−1.
By definition of labeling, label of each vertex must be different i.e.,ϕxi≠ϕyj,ϕxi≠ϕzk, and ϕyj≠ϕzk, otherwise, if ϕxi=ϕyj for some i and j, then ϕxi+ϕzk=ϕyj+ϕzk i.e., wϕxizk=wϕyjzk. Last vertex zn of T3,n has label nn2+2. Further weights of edge are given as follows:(21)wϕxiy1=ϕxi+ϕy1=n+1+i,1≤i≤n,wϕxiyj+1=ϕxi+ϕyj+1=n+1+nj+i,1≤i≤n,1≤j≤n−1,wϕxiz1=ϕxi+ϕz1=n2+n+1+i,1≤j≤n,wϕxizk+1=ϕxi+ϕzk+1=k+1n2+1+n+i,1≤i≤n,1≤k≤n−1,wϕy1z1=ϕy1+ϕz1=n2+2n+1,wϕy1zk+1=ϕy1+ϕzk+1=k+1n2+1+2n+1,1≤k≤n−1,wϕyj+1z1=ϕyj+1+ϕz1=2n+1+nj+n2,1≤j≤n−1,wϕyj+1zk+1=ϕyj+1+ϕzk+1=k+1n2+1+nj+2n+1,1≤j≤n−1,1≤k≤n−1.
Edge weights are distinct for all pairs of distinct edges, i.e., for any two edgese and fwϕe≠wϕf. Thus, the vertex labeling is an edge irregular nn2+2 labeling. Hence, we get eisT3,n=nn2+2. Furthermore, we can have eisT4,n=n2+12+n2 and eisT5,n=nn2+22−1.Example 5.
The diagram in Figure5 is the example of irregular labeling of T3,4 that carries eisT3,4=72.Figure 5
Irregular labeling ofT3,4 with eisT3,4=72.


## 2.1. Middle Graph of Path Graph

Ifk vertices ai:1≤i≤k carry a path Pk, and bi:1≤i≤k−1 is another set of vertices. Then the graph MPk is said to be middle graph of path graph including the sets of vertices and edges, respectively, given as follows:(1)VMPk=ai:1≤i≤k∪bi:1≤i≤k−1,eMPk=aiai+1:1≤i≤k−1∪aibi:1≤i≤k−1∪biai+1:1≤i≤k−1.


## 2.2. Middle Graph of Cycle Graph

IfCk is cycle of k vertices xj:1≤j≤k and yj:1≤j≤k is another set of vertices. Then the graph MCk is said to be middle graph of cycle graph including the sets of vertices and edges, respectively, given as follows:(2)VMCk=xj:1≤j≤k∪yj:1≤j≤k,eMCk=xjxj+1:1≤j≤k−1∪xkx1∪xjyj:1≤j≤k∪yjxj+1:1≤j≤k−1∪ykx1.


## 2.3. Ceiling Function

We define ceiling function asy=⌈fx⌉, when image of any value is in fraction like 5/2, we take this value as 3.Theorem 1.
LetMPq is middle graph of the path graph Pq with q≥2. Then eisMPq=2q−1.Proof.
ConsiderPq be path graph of q vertices, MPq is middle graph of the path graph including the following sets, vMPq and eMPq, of vertices and edges, respectively, given as follows:(3)vMPq=um:1≤m≤q∪vn:1≤n≤q−1,eMPq=uiui+1:1≤i≤q−1∪ujvj:1≤j≤q−1∪vkuk+1:1≤k≤q−1.
Order of graphMPq is 2q−1 and size is 3q−1. Presently, we characterize a mapping α:V⟶1,2,3,…,2q−1 as follows:(4)αui=2i−1,1≤i≤q,αvj=2j,1≤j≤q−1.
Degree of eachui2≤i≤q−1 is 4 and degree of u1, uq, and vj1≤j≤q−1 is 2. No two vertices have same labels for irregular labeling. The label of vertex uq is 2q−1 which is edge strength of MPq. Weights of edges are given as follows:(5)wαuiui+1=αui+αui+1=4i,1≤i≤q−1,wαujvj=αuj+αvj=4j−1,1≤j≤q−1,wαvkvk+1=αvk+αvk+1=4k+1,1≤k≤q−1.
Edge weights are distinct for all distinct edges, i.e., for any two edgese and fwαe≠wαf. Thus apex (vertex) labeling is an edge irregular 2q−1 labeling. Hence, we have eisMPq=2q−1.Example 1.
The diagram in Figure1 is the example of irregular labeling of MQ6 that carries eisMQ6=11.Figure 1
Irregular labeling ofMQ6 with eisMQ6=11.Theorem 2.
LetCr,r≥2 is Cycle graph, MCr is middle graph of cycle graph. Then(6)eisMCr=2r−1for risodd2r+1for riseven.Proof.
LetCr be a cycle graph of r vertices and MCr is middle graph including VMCr and EMCr as vertex set and edge set, respectively, given as follows:(7)VMCr=pl:1≤l≤r∪qm:1≤m≤r,EMCr=piqi+1:1≤i≤r−1∪pjqj:1≤j≤r∪qkpk+1:1≤k≤r−1∪qrp1∪prp1.
The order ofMCr is 2r and size is 3r, while the degree of each pi is 4 and the degree of each qi is 2 and no two vertices have same labels for irregular labeling. In this graph there are two possible cases.Case-i: whenr is odd we define function β:VMCr⟶1,2,3,…,2r−1 as follows:(8)βpi=2i−1,1≤i≤r,βqj=2j,1≤j≤r−1,βqr=5.Weights of edges are as follows:(9)wβpipi+1=βpi+βpi+1=4i,1≤i≤r−1,wβprp1=βpr+βp1=2r,wβpjqj=βpj+βqj=4j−1,≤k≤r−1,wβqkpk+1=βqk+βpk+1=4k+1,1≤k≤r−1,wβprq1=βpr+βq1=6,wβprqn=βpr+βqn=2r+4.Here distinct edges carry distinct weights, i.e., for any two edgese and fwβe≠wβf. Last vertex pr of Cr has label 2r−1. Thus, vertex labeling β is an edge irregular 2r−1 labeling. Hence eisG=2r−1.Case-ii: for evenr we define transformation β:VMCr⟶1,2,3,…,2r+1 as follows:(10)βpi=2i−1,1≤i≤r−1,βpr=2r+1,βqj=2j,1≤j≤r−1,βqr=5.
Weights of edges in this case are given as follows:(11)wβpipi+1=βpi+βpi+1=4i,1≤i≤r−2,wβpn−1pn=βpn−1+βpn=4n+2,wβpjqj=βpj+βqj=4j−1,1≤j≤r−2,wβpnqn=βpn+βqn=2n+6,wβqkpk+1=βqk+βpk+1=4k+1,1≤k≤r−1,wβpnq1=βpn+βq1=6.
Here the edge weights are distinct for all pairs of distinct edges i.e., for any two edgese and fwβe≠wβf, and last vertex pr of Cr has label 2r+1. Therefore, labeling is an edge irregular 2r+1 labeling. Hence, we have eisG=2r+1.Example 2.
The diagram in Figure2 is the example of irregular labeling of MC10 that carries eisMC10=21.Figure 2
Irregular labeling ofMC10 with eisMC10=21.Theorem 3.
Pm1 is path with m1 vertices and K2,n1 is complete bipartite graph. Graph G=K2,n1ΔPm1 is paramedian ladder graph. Then(12)eisG=2m1n1+1−12.Proof.
letE2G and V2G are the edge and vertex sets, respectively, of the graph G.(13)V2G=uij:1≤i≤n1,1≤j≤m1∪vk:1≤k≤2m1,E2G=uijvk:1≤i≤n1,1≤j≤m1,1≤k≤2m1∪u1ju1j+1:1≤j≤m1−1∪un1jun1j+1:1≤j≤m1−1.
The order ofG is m1n1+2 and size is 2m1n1+1−2. From Theorem A, eisG≥max⌈2m1n1+2m1−1/2⌉,ΔG. ΔG represents degree of the graph. Since degree of G is n1 so eisG≥⌈2m1n1+2m1−1/2⌉. To show equality it suffices to prove existence of an edge irregular ⌈2m1n1+2m1−1/2⌉ labeling. For this we define mapping ϕ:V⟶1,2,3,…,2m1n1+2m1−1/2 as follows:(14)ϕui2j−1=2n1+1j−1+i,1≤i≤n1,1≤j≤m1,ϕun1−12j=2jn1+1−n1,1≤j≤m1,ϕun12j=2jn1+1−n1+1,1≤j≤m1′ϕun1−i2j=2jn1+1−n1+i,1≤j≤m1,2≤i≤n1−1,ϕv2i=in1+1,1≤i≤n1,ϕv2i−1=in1+1−n1,1≤i≤n1.
Weights of edges are given as follows:(15)wϕv2k−1ui2j−1=ϕv2k−1+ϕui2j−1=2j−1+kn1+1+i−n1,1≤i≤n1,1≤j≤m1,k≅1mod2,wϕv2k−1un1−12j=ϕv2k−1+ϕun1−12j=2j+kn1+1−2n1,1≤j≤m1,k≅0mod2,wϕv2k−1un12j=ϕv2k−1+ϕun12j=2j+kn1+1−2n1+1,2≤i≤n1−1,1≤j≤m1,k≅0mod2,wϕv2k−1un1−i2j=ϕv2k−1+ϕun1−i2j=2j+kn1+1−2n1+i,2≤i≤n1−1,1≤j≤m1,k≅0mod2,wϕv2kui2j−1=ϕv2k+ϕui2j−1=2j−1+kn1+1+i,1≤i≤n1,1≤j≤m1,k≅1mod2,wϕv2kun1−12j=ϕv2k+ϕun1−12j=2j+kn1+1−n1,1≤j≤m1,k≅0mod2,wϕv2kun12j=ϕv2k+ϕun12j=2j+kn1+1−n1+1,1≤j≤m1,k≅0mod2,wϕv2kun1−i2j=ϕv2k+ϕun1−i2j=2j+kn1+1−n1+i,2≤i≤n1−1,1≤j≤m1,k≅0mod2.
Weights form (2,1) irregular labeling. For any two different edges, their loads are different. Thus vertex labeling is an edge irregular⌈2m1n1+1−1/2⌉ labeling. Hence, we get eisG=⌈2m1n1+1−1/2⌉.Example 3.
The diagram in Figure3 is the example of irregular labeling of G=K2,6△P4 that carries eisG=28.Figure 3
Irregular labeling ofG=K2,6△P4 with eisG=28.Theorem 4.
Theorem 4.LetGV,E be a snake graph of n-rectangles with string 2,2,…,2. Then eisG=⌈4n+1/2⌉.Proof.
Let snake graphG with n-rectangles includes following sets V and E of vertices and edges, respectively,(16)V=ui:1≤i≤n+1∪vj:1≤j≤n∪wk:1≤k≤n,E∪wlul+1:1≤l≤n.
The order ofG is 3n+1 and size is 4n. From Theorem A, eisG≥max⌈4n+1/2⌉, ΔG. Since max degree of G is 4 so eisG≥⌈4n+1/2⌉. To show equality, it suffices to prove existence of an edge irregular ⌈4n+1/2⌉ labeling. For this we define mapping γ:V⟶1,2,3,…,4n+1/2 as follows:(17)γvi=2i−1,1≤i≤n,γuj=2j−1,1≤j≤n+1,γwk=2k,1≤k≤n.
Last vertexun+1 of G has label ⌈4n+1/2⌉. Furthermore, the weights of edges are given by(18)wγuivi=γui+γvi=4i−2,1≤i≤n,wγvjuj+1=γvj+γuj+1=4j,1≤i≤n,wγukwk=γuk+γwk=4k−1,1≤k≤n,wγwlul+1=γwl+γul+1=4l+1,1≤l≤n.
Edge weights are distinct for all pairs of distinct edges i.e., for any two edgese and fwγe≠wγf. Thus, vertex labeling is an edge irregular ⌈4n+1/2⌉ labeling. Hence, we have eisG=⌈4n+1/2⌉.Example 4.
The diagram in Figure4 is the example of irregular labeling of a snake graph G of 5-strings and carries eisG=11.Figure 4
Irregular labeling of a snake graphG of 5-strings with eisG=11.Theorem 5.
LetTm,n be a m-partite complete graph with m set of vertices and each set contains n vertices. Then for m = 3, eisT3,n=nn2+2.Proof.
letVT3,n and ET3,n denote the vertex set and edge set of T3,n, respectively,(19)VT3,n=xi:1≤i≤n∪yj:1≤j≤n∪zk:1≤k≤n,ET3,n=xiyj:1≤i≤n,1≤j≤n∪xizk:1≤i≤n,1≤k≤n∪yjzk:1≤j≤n,1≤k≤n.
The order of the graphT3,n is 3n and size is 3n2. Since eisG≥max⌈E+1/2⌉,ΔG. Max degree of G is n. Now we define function ϕ:V⟶1,2,…,nn2+2 such that(20)ϕxi=i,1≤i≤n,ϕy1=n+1,ϕyj+1=n+1+jn,1≤j≤n−1,ϕz1=n2+n+1,ϕzk+1=k+1n2+1+n,1≤k≤n−1.
By definition of labeling, label of each vertex must be different i.e.,ϕxi≠ϕyj,ϕxi≠ϕzk, and ϕyj≠ϕzk, otherwise, if ϕxi=ϕyj for some i and j, then ϕxi+ϕzk=ϕyj+ϕzk i.e., wϕxizk=wϕyjzk. Last vertex zn of T3,n has label nn2+2. Further weights of edge are given as follows:(21)wϕxiy1=ϕxi+ϕy1=n+1+i,1≤i≤n,wϕxiyj+1=ϕxi+ϕyj+1=n+1+nj+i,1≤i≤n,1≤j≤n−1,wϕxiz1=ϕxi+ϕz1=n2+n+1+i,1≤j≤n,wϕxizk+1=ϕxi+ϕzk+1=k+1n2+1+n+i,1≤i≤n,1≤k≤n−1,wϕy1z1=ϕy1+ϕz1=n2+2n+1,wϕy1zk+1=ϕy1+ϕzk+1=k+1n2+1+2n+1,1≤k≤n−1,wϕyj+1z1=ϕyj+1+ϕz1=2n+1+nj+n2,1≤j≤n−1,wϕyj+1zk+1=ϕyj+1+ϕzk+1=k+1n2+1+nj+2n+1,1≤j≤n−1,1≤k≤n−1.
Edge weights are distinct for all pairs of distinct edges, i.e., for any two edgese and fwϕe≠wϕf. Thus, the vertex labeling is an edge irregular nn2+2 labeling. Hence, we get eisT3,n=nn2+2. Furthermore, we can have eisT4,n=n2+12+n2 and eisT5,n=nn2+22−1.Example 5.
The diagram in Figure5 is the example of irregular labeling of T3,4 that carries eisT3,4=72.Figure 5
Irregular labeling ofT3,4 with eisT3,4=72.


## 3. Conclusion

In this manuscript, we have examined the labeling of some families of graphs in an irregular manner and also introducedEIS as a modification of different strengths like TVIS and a total EIS. We got a few estimations on the EIS and find precise incentives for certain families of graphs namely the middle graph of path, middle graph of cycle, snake graph, string 2, paramedian ladder, and complete m-partite graphs. The value of eisG can help for calculate the spanning trees for these type of graph. The graph labeling has wide range of applications such as x-rays crystallography, coding theory, radar, astronomy, and communication design. By raising the open problem, we conclude this section [14, 15].


### 3.1. Open Problem 1

For any positive integersm, n generalization of edge irregularity strength of m-partite graph is Tm,n, i.e., eisTm,n for m≥6.


## 3.1. Open Problem 1

For any positive integersm, n generalization of edge irregularity strength of m-partite graph is Tm,n, i.e., eisTm,n for m≥6.



---

*Source: 3230932-2022-11-28.xml*