# On EdgeH-Irregularity Strength of Hexagonal and Octagonal Grid Graphs

Authors: Muhammad Ibrahim; Ana Gulzar; Muhammad Fazil; Muhammad Naeem Azhar
Journal: Journal of Mathematics
 (2022)

---

## Abstract

The edgeH-irregularity strength, ehsΓ,H, of a graph Γ is the smallest integer k, such that Γ has an H-irregular edge k-labeling. In this study, we compute the exact value of edge H-irregularity strength of hexagonal and octagonal grid graphs.


---

## Body

## 1. Introduction

LetΓ be a connected graph. A mapping that assigns numbers to graph elements (vertices and edges) is called labeling. A graph labeling is called vertex labeling or edge labeling if its domain set is the vertex set or the edge set of the graph, respectively. The concept of graph labeling plays an important role to construct models for a wide range of engineering applications such as coding theory, X-rays crystallography, astronomy, radar, circuit design, wired communication, and wireless communications. For further detail related to graph labeling, refer to [1].For an edgek-labeling ζ:EΓ⟶1,2,…,k, k∈ℤ+, the corresponding weight of u∈VΓ is wtζu=∑uv∈EΓζuv. The edge k-labeling ζ is called irregular if wtζu≠wtζv, ∀u≠v∈VΓ. The irregularity strength of Γ, sΓ, is the minimum k∈ℤ+, such that there exists an edge irregular k-labeling of Γ. The concept of the irregularity strength of a graph was introduced by Chartrand et al. [2]. There has been a flurry of research work on the irregularity strength in the last few years [3–12].A vertexk-labeling ζ∗:VΓ⟶1,2,…,k of Γ is called an edge irregular k-labeling if for every two distinct edges uv and u′v′, wtζ∗uv≠wtζ∗u′v′, where wtζ∗uv=ζ∗u+ζ∗v. The edge irregularity strength of Γ, esΓ, is the minimum k, such that the graph Γ has an edge irregular k-labeling. The concept of the edge irregularity strength was given by Ahmad et al. [13]. Ashraf et al. [14] have introduced two new graph parameters, i.e., vertex (edge) H-irregularity strength of a graph. These parameters are considered as extensions of the irregularity strength and the edge irregularity strength of Γ.A familyℋ=Hi,1≤i≤t of subgraphs of a graph Γ, such that each edge of Γ belonging to at least one member of ℋ is called an edge-covering of Γ. If every member of ℋ is isomorphic to a graph H, then Γ admits an H-covering. An edge k-labeling ζ is called an H-irregular edge k-labeling of the graph Γ that admits H-covering if for every two distinct subgraphs H1 and H2, which are isomorphic to H, wtζH1≠wtζH2. The edge H-irregularity strength of a graph Γ, ehsΓ,H, is the smallest integer k, such that Γ has an H-irregular edge k-labeling.In proving lower bound concerning a graphΓ admitting H-covering, the following result is useful.Theorem 1 (see [14]).
LetΓ be a graph admitting H-covering given by t subgraphs isomorphic to H. Then, ehsΓ,H≥1+t−1/EH.In this study, we compute the exact values of the edgeH-irregularity strength of the hexagonal grid graph and octagonal grid graph.


## 2. Motivation and Applications ofH-Covering of Graph

The topic ofH-covering of the graph is newly addressed by Ashraf et al. in [14] and found the H-covering for different graphs. Still now, the problem of H-covering was addressed on grids by any author. As the topic is related to the networking and communication system, it is needed to work on some networks. So, we choose these two graphs as these graphs are related to network. The H-covering has a wide range of applications in X-rays, circuit design, and especially in communication and networks. The graphs studied in the present study are hexagonal and octagonal grids. These graphs consist of 6 and 8 vertices in each face of the graph, and each face made a cycle consisting of 6 and 8 vertices and edges as well. These graphs and their faces could be served as models for surveillance or security systems, electrical switchboards, circuit design, and communication networks. These networks can be extended in both horizontal and vertical directions, so that the extension in the graphs and networks can be handled and made easy. Moreover, these networks are used especially in communication networks, and the efficiency of the networks may be improved as the weights of the each face have distinct numbers.


## 3. Hexagonal Grid Graph

For finiter,s≥3, the hexagonal grid graph (honeycomb), Hrs, is a graph with s rows and r columns of hexagons [15]. The vertex and the edge sets of this graph are defined as VHrs=vji,uji;1≤i≤s,1≤j≤r;EHrs=vjiuji,vji+1uji+1;1≤i≤s−1,1≤j≤r∪vjiuj+1i,uji+1vj+1i+1;1≤i≤s−1,1≤j≤r−1∪ujivji+1;1≤i≤s−1,1≤j≤r. The face set of FHrs consists of FHrs−1 6-sided faces and one external face which is infinite. Also, VHrs=2rs−2 and EHrs=VHrs+sr−1, while FHrs=4r+s−9. For r,s≥3, the hexagonal grid graph is shown in Figure 1.Figure 1
Hexagonal grid graphHrs.In the following theorem, we determine the edgeH-irregularity strength of Hrs, where r,s≥3 are finite.Theorem 2.
For hexagonal grid graphHrs, r,s≥3 admitting an H-covering given by r−1s−1 subgraphs isomorphic to C6, ehsHrs,C6=1+r−1s−1−1/6.Proof.
The graphHrs,r,s≥3 obviously admits a C6-covering with exactly r−1s−1 subcovers of C6. Set k=1+r−1s−1−1/6; then, k is the lower bound of ehsHrs,C6 by Theorem 1. Now, to prove the converse inequality, we have to describe a C6−irregular edge k-labeling ζ:EC6⟶1,2,…,k as follows:Case 1: whens is odd,(1)ζvjiuji=ζvji+1uji+1=1,fori=1;1≤j≤r,j2,fori=2;1≤j≤2ir−1+56,ir−1+56,fori=2;2ir−1+56+1≤j≤r,i−1r−1+56,for3≤i≤s−1;iisodd,1≤j≤r,ir−1+56,for4≤i≤s−1;iiseven,1≤j≤r,(2)ζvjiuj+1i=ζuji+1vj+1i+1=1,fori=1;1≤j≤r−1,jisodd,2,fori=1;2≤j≤r−1,jiseven,j2,fori=1;1≤j≤2ir−1+56,i+1r−1+56,fori=2;2ir−1+56+1≤j≤r−1,i−1r−1+56,for3≤i≤s−1;iisodd,1≤j≤r−1,j,fori=4;1≤j≤ir−1+56,ir−1+56,fori=4;ir−1+56+1≤j≤r−1,ir−1+56,for6≤i≤s−1;iiseven,1≤j≤r−1,(3)ζujivji+1=1,fori=1;1≤j≤r,r+3−2ir−1+5/62,fori=2;for1≤j≤2ir−1+56+jisodd,r+3−2ir−1+5/62,fori=2;for2≤j≤2ir−1+56+jiseven,j−2ir−1+5/62+r+3−2ir−1+5/62,fori=2;for2ir−1+56+1≤j≤r,jisodd,r+3−2ir−1+52−j−2ir−1+5/62,fori=2;for2ir−1+56+1≤j≤r,jiseven,i−1r−1+5−2i−1r−1+5/6−i+1r−1+5/62,fori=3;for1≤j≤i+1r−1+56+1,jisodd,j−1i+1r−1+5/62+2r−1+6−2i−1r−1+5/6−i+1r−1+5/62,fori=3;i+1r−1+56+2≤j≤r,2r−1+5−2i−1r−1+5/6−i+1r−1+5/62,fori=3;for2≤j≤i+1r−1+56+1,jiseven,(4)ζujivji+1=j−1−i+1r−1+5/62+2r−1+5−2i−1r−1+5/6−i+1r−1+5/62,fori=3;i+1r−1+56+2≤j≤r,3r−1+5−3ir−1+5/62,fori=4;1≤j≤ir−1+56+1,jisodd,3r−1+5−3ir−1+5/62+j−1−ir−1+5/62,fori=4;ir−1+56+2≤j≤r,3r−1+5−3ir−1+5/62,fori=4;2≤j≤ir−1+56+1,jiseven,3r−1+5−3ir−1+5/62+j−1−ir−1+5/62,fori=4;ir−1+56+2≤j≤r,i−1r−1+6−2i−1r−1+5/6−2i+1r−1+5/62+j2−1,for5≤i≤s−1;iisodd,1≤j≤r,jisodd,i−1r−1+6−2i−1r−1+5/6−2i+1r−1+5/62+j2−1,for5≤i≤s−1;iisodd,2≤j≤r,jiseven,i−1r−1+6−4ir−1+5/62+j2−1,for6≤i≤s−1;iiseven,1≤j≤r,jisodd,i−1r−1+6−4ir−1+5/62+j2−1,for6≤i≤s−1;iiseven,1≤j≤r,jiseven.Case 2: whens is even,(5)ζvjiuji=ζvji+1uji+1=j3,fori=1;1≤j≤3,j+36,fori=1;4≤j≤r,j6,fori=2;1≤j≤r,ir−1+56−1,forr=3,i=3;j=1,ir−1+56−2,forr>3,i=3;j=1,ir−1+56−1,fori=3;j=2,ir−1+56,fori=3;3≤j≤r,i−1r−1+56,for4≤i≤s−1,iiseven;1≤j≤r,ir−1+56−2,fori=5;j=1,ir−1+56−1,fori=5;j=2,ir−1+56,fori=5;3≤j≤r,ir−1+56−1,for7≤i≤s−1,iisodd;1≤j≤r,ζvjiuj+1i=ζuji+1vj+1i+1=j5,fori=1;1≤j≤5,j+16,fori=1;6≤j≤r−1,j4,fori=2;1≤j≤4,j+26,fori=2;5≤j≤r−1,ir−1+56,for3≤i≤s−1;iisodd,1≤j≤r−1,i−1r−1+56,for4≤i≤s−1;iiseven,1≤j≤r−1,(6)ζujivji+1=j2,fori=1;1≤j≤2,j+46,fori=1;3≤j≤r,i−1r−1+4−2i+1r−1+5/6+r/132,fori=2;j=1,3,i−1r−1+4−2i+1r−1+5/6+r/142,fori=2;j=2,i−1r−1+4−2i+1r−1+56+j−13,forriseven,i=2;for4≤j≤r,jiseven,i−1r−1+4−2i+1r−1+56+r14+j−13,forriseven,i=2;for5≤j≤r,jisodd,i−1r−1+2−2i+1r−1+56+r14+j−13,forrisodd,i=2;for4≤j≤r,jiseven,i−1r−1+4−2i+1r−1+5/6+r/132+j−23,forrisodd,i=2;for5≤j≤r,jisodd,i−1r−1+6−4ir−1+5/6+2r/132,fori=3;1≤j≤4,i−1r−1+6−4ir−1+5/6+2r/132+j−42,fori=3;5≤j≤r,ir−1+6−3i+1r−1+5/6−2i−1r−1+5/6+r/142,forrisodd,i=2;j=1,3,ir−1+4−3i+1r−1+5/6−2i−1r−1+5/6−r/12+3r/132,forriseven,i=4;j=1,3,ir−1+9−3i+1r−1+5/6−2i−1r−1+5/62,forr=3,5,i=4;j=2,ir−1+4−3i+1r−1+5/6−2i−1r−1+5/6+3r/142,forrisodd;r>5,i=4;j=2,ir−1+5−3i+1r−1+5/6−2i−1r−1+5/6+2r/13−r/122,forriseven,i=4;j=2,ir−1+9−3i+1r−1+5/6−2i−1r−1+5/62+j−32,forr=5,i=4;4≤j≤r,ir−1+4−3i+1r−1+5/6−2i−1r−1+5/6+3r/142+j−32,forrisodd;r≠5,i=4;for4≤j≤r,ir−1+6−3i+1r−1+5/6−2i−1r−1+5/6+r/13−r/122+j−32,forriseven,i=4;for4≤j≤r,jiseven,ir−1+4−3i+1r−1+5/6−2i−1r−1+5/6+3r/132+j−32,forrisodd,i=4;for5≤j≤r,jisodd,i−1r−1+4−4ir−1+5/6+4r/132,fori=5;1≤j≤4,i−1r−1+4−4ir−1+5/6+4r/13+j−4/252,fori=5;5≤j≤r,(7)ζujivji+1=i−1r−1+6−2i−1r−1+5/6−2i+1r−1+5/6+5r/132+j2−1,for6≤i≤s−1;iiseven;for1≤j≤r,jisodd,i−1r−1+6−2i−1r−1+5/6−2i+1r−1+5/6+5r/132+j2−1,for6≤i≤s−1;iiseven;for1≤j≤r,jiseven,i−1r−1−2i−1r−1+5/6−2i+1r−1+5/6+4r/132+j2−1,forr=3;1≤j≤r;for7≤i≤s−1,iisodd,i−1r−1+6−2i−1r−1+5/6−2i+1r−1+5/62+j2−1,forrisodd,3<r≤13;1≤j≤r;for7≤i≤s−1,iisodd,i−1r−1+6−2i−1r−1+5/6−2i+1r−1+5/6+4r/142+j2−1,forr=15+6k,k≥0;1≤j≤r;for7≤i≤s−1,iisodd,i−1r−1+8−2i−1r−1+5/6−2i+1r−1+5/6+4r/142+j2−1,forrisodd,r≥17;1≤j≤r;for7≤i≤s−1,iisodd,i−1r−1+2−2i−1r−1+5/6−2i+1r−1+5/6+4r/142+j2−1,forr=even0mod6;1≤j≤r;for7≤i≤s−1,iisodd,i−1r−1+4−2i−1r−1+5/6−2i+1r−1+5/6+4r/132+j2−1,forr=even2mod6;1≤j≤r;for7≤i≤s−1,iisodd,i−1r−1−2i−1r−1+5/6−2i+1r−1+5/6+4r/152+j2−1,forr=even4mod6;1≤j≤r;for7≤i≤s−1,iisodd.
Figure2 shows the weights of the edge C6-covering of the hexagonal grid graph, and the formula for the weights of the edge C6-covering is given as follows: wtζC6vjiujivji+1uji+1vjiuj+1iuji+1vj+1i+1ujivji+1=5+i−1r−1+j,1≤i≤s;1≤j≤r. Observe that all the weights of subcovers of C6 are distinct. Hence, ehsHrs,C6=1+r−1s−1−1/6, which completes the proof of this theorem.Figure 2
Labeling and weights of hexagonal grid graphH66.


## 4. Octagonal Grid Graph

For finiter,s≥3, the octagonal grid graph, Ors, is a graph with s rows and r columns of octagons [16]. The vertex and the edge sets of this graph are defined as VOrs=vji,xji;for1≤i≤s,1≤j≤r∪uji,xji;1≤i≤s−1,1≤j≤r;EOrs=vjiuji,xjiuj+1i,wji+1vji+1,xji+1wj+1i;1≤i≤s−1,1≤j≤r−1∪ujiwji;1≤i≤s−1,1≤j≤r∪vjixji;for1≤i≤s,≤j≤r−1. The face set of FOrs consists of FOrs−1 faces as 8-sided faces and one external face which is infinite. Also, VOrs=4rs−2r+s and EOrs=VOrs+r2s−1−3s+2, while FOrs=2r−12s−1.Forr,s≥3, the octagonal grid graph is shown in Figure 3.Figure 3
Octagonal grid graphOrs.The following result establishes the edgeH-irregularity strength of Ors for 3≤r≠12,14≤15 and s≥3.Theorem 3.
LetOrs be an octagonal grid graph admitting C8-covering given by r−1s−1 subgraphs isomorphic to H; then, ehsOrs=1+r−1s−1−1/8.Proof.
It is clear that the graphOrs for 3≤r≤15 and s≥3 and r≠12,14 admits C8-covering with exactly r−1s−1 subcovers of C8. Set k=1+r−1s−1−1/8; then, k is the lower bound of ehsOrs,C8 by Theorem 1. Now, to prove the converse inequality, we have to describe a C8−irregular edge k-labeling ζ:EC8⟶1,2,…,k given as follows:Case 1: when3≤r≤7 and s≥3, 1≤i≤s−1;1≤j≤r−1,(8)ζvjiuji=r−1i−1+j8,ζxjiuj+1i=r−1i−r−2/2+j8,ζxji+1wj+1i=r−1i5−r/2+j8,(9)ζwjivji+1=r−1i−1+1+j8,forr=4,5,6,1≤i≤s−1;1≤j≤r−1,r−1i−1+2+j8,forr=3,7,1≤i≤s−1;1≤j≤r−1,(10)ζujiwji=r−1i−1+5+j8,forr=4,5,6,7,1≤i≤s−1;1≤j≤r,r−1i+48,forr=3,1≤i≤s−1;1≤j≤r,(11)ζvjixji=r−1i−2+7+j8,for1≤i≤s;1≤j≤r−1.Case 2: when8≤r≤13, r≠12,14 and s≥3, 1≤i≤s−1;1≤j≤r−1,(12)ζxjiuj+1i=r−1i−1+3+j8,ζwjivji+1=r−1i−1+2+j8,ζxji+1wj+1i=r−1i−1+4+j8,(13)ζvjiuji=r−1i−1+1+j8,forr=8,9,10,11,1≤i≤s−1;1≤j≤r−1,r−1i−1+2+j8,forr=13,1≤i≤s−1;1≤j≤r−1,(14)ζujiwji+1=r−1i−1+5+j8,for1≤i≤s−1;1≤j≤r,(15)ζvjixji+1=r−1i−1+j8,forr=8,1≤i≤s;1≤j≤r−1,r−1i−r+j8+1,forr=9,1≤i≤s,iisodd;j=1,r−1i−r+j8,forr=9,1≤i≤s,iisodd;2≤j≤r−1,r−1i−r+j8,forr=9,1≤i≤s,iiseven;1≤j≤r−1,r−1i−r+j8−−1i,forr=10,11,1≤i≤s;j=1,r−1i−r+j8,forr=10,11,1≤i≤s;1≤j≤r−1,r−1i−r+j8−−1i,forr=13,1≤i≤s;1≤j≤4,r−1i−r+j8,forr=13,1≤i≤s;5≤j≤r−1.Case 3: whenr=15 and s≥3, 1≤i≤s−1;1≤j≤r−1,(16)ζvjiuji=r−1i−1+1+j8,ζxjiuj+1i=r−1i−1+3+j8,ζwjivji+1=r−1i−1+4+j8,(17)ζxji+1wj+1i=r−1i−1+5+j8,(18)ζujiwji=r−1i−1+6+j8,for1≤i≤s;1≤j≤r,(19)ζvjixji=r−1i−1−4+j8−−1i,for1≤i≤s−1;1≤j≤6,r−1i−1−4+j8,for1≤i≤s;1≤j≤r−1.
Figure4 shows the weights of the edge C8-covering of the octagonal grid graph, and the formula for the weights of the edge C8-covering is given as follows:(20)wtζc8vjiujixjiuj+1iwjivji+1xji+1wj+1iujiwjivjixji=7+i−1r−1+j,1≤i≤s;1≤j≤r−1.
Observe that all the weights of subcovers ofC8 are distinct. Hence, ehsOrs,C8=1+r−1s−1−1/8, which completes the proof of this theorem.Figure 4
Labeling and weights of octagonal grid graphO55.


## 5. Conclusion

In this study, we have determined the edgeH-irregularity strength for the hexagonal grid graphs Hrs for r,s≥3 and the octagonal grid graphs Ors for r,s≥3. We have tried to find the edge H-irregularity strength of octagonal grid graph Ors for r≥12 (r is even) and s≥17 (s is odd), but so far without success. Hence, we conclude the study with the following open problems.Open Problem 1.
LetOrs be an octagonal grid graph admitting C8-covering. Then, ehsOrs,C8=1+r−1s−1−1/8 for r>12riseven and for r≥17risodd.Open Problem 2.
LetOrs be an octagonal grid graph admitting C8-covering. Then, ehsOrs,C8=1+r−1s−1−1/8 for r≥3, r≥3 for any choice of r and s.



---

*Source: 6047926-2022-01-31.xml*