# On Total Vertex Irregularity Strength of Hexagonal Cluster Graphs

Authors: Nurdin Hinding; Hye Kyung Kim; Nurtiti Sunusi; Riskawati Mise
Journal: International Journal of Mathematics and Mathematical Sciences
 (2021)

---

## Abstract

For a simple graphG with a vertex set VG and an edge set EG, a labeling f:VG∪​EG⟶1,2,⋯,k is called a vertex irregular total k−labeling of G if for any two different vertices x and y in VG we have wtx≠wty where wtx=fx+∑u∈VGfxu. The smallest positive integer k such that G has a vertex irregular total k−labeling is called the total vertex irregularity strength of G, denoted by tvsG. The lower bound of tvsG for any graph G have been found by Baca et. al. In this paper, we determined the exact value of the total vertex irregularity strength of the hexagonal cluster graph on n cluster for n≥2. Moreover, we show that the total vertex irregularity strength of the hexagonal cluster graph on n cluster is 3n2+1/2.


---

## Body

## 1. Introduction

A graph labeling is an assignment of integers from 1 ton, for the vertices, edges, or both. Graph labelings have been used in many applications like communication network addressing, software testing, information security, technology and sports tournament scheduling, and coding theory problems including the design of good radar location codes, missile guidance codes, and convolution codes.We consider the finite undirected graphG without loops and multiple edges with vertex set VG and edge set EG. The degree of a vertex x is the number of edges that have x as an endpoint, and the set of neighbors of x is denoted by Nx. If the domain of the labeling function fx is the vertex set or the edge set, the labeling is called, respectively, vertex labeling or edge labeling. If the domain is VG∪​EG, then we call the labeling a total labeling.A labelingf:EG⟶1,2,3,⋯,k is called an edge k−labeling of G. The associated vertex weight of a vertex x∈VG under an edge k−labelingf is defined as wtx=∑v∈Nxfxv. Chartrand et al. [1] introduced an edge k−labeling of a graph G such that wtx≠wty for all vertices x,y∈VG with x≠y. Such labelings were called irregular assignments, and the irregularity strength sG of a graph G is known as the minimum k for which G has an irregular assignment using labels at most k. The irregularity strength sG can be interpreted as the smallest integer k for which G can be turned into a multigraph G′ by replacing each edge by a set of at most k parallel edges, such that the degrees of the vertices in G′ are all different.In this paper, we consider for a totalk−labeling of G, that is, f:VG∪​EG⟶1,2,3,⋯,k. The associated vertex weight of a vertex x∈VG under a total k−labelingf is defined as wtx=fx+∑v∈Nxfxv. A total k−labelingf is defined to be a vertex irregular total k−labeling of G if for every two different vertices x and y of G, wtx≠wty. The minimum positive integer k for which G has a vertex irregular total k−labeling is called the total vertex irregularity strength of G, denoted by tvsG. In Figure 1, there are a two total labeling of P4, one of is a vertex irregular total 3-labeling of P4 and the other is a vertex irregular total 2-labeling of P4. However, P4 does not have a vertex irregular total vertex 1-labeling. Such that the minimum positive integer k for which P4 has a vertex irregular total k−labeling is 2, or the total vertex irregularity strength of P4 is 2.Figure 1
A vertex irregular totalk-labeling of P4 for k=2 and k=3.
(a)(b)Baca et al. [2] in 2007 started to investigate the total vertex irregularity strength of a graph, an invariant analogous to the irregularity strength for total labelings. There are not many graphs for which the exact values of their total vertex irregularity strength are known. Baca et al. [2] have determined the total vertex irregularity strengths for some classes of graphs, namely, cycles, stars, and prisms. Nurdin et al. have determined the total vertex irregularity strengths of a disjoint union of t copies of a path [3], tree graphs [4], and caterpillar graph [5]. Nurdin and Kim have determined the total vertex irregularity strength of splitting graphs of stars [6].In this paper, we determine exact value of the total vertex irregularity strength of the hexagonal cluster graph withn cluster for n≠2.


## 2. Hexagonal Cluster Graph

In this section, we give the definition of hexagonal cluster graphs. The hexagonal cluster graph withn≥2 cluster, denoted by HCn, where HC1 isomorphs to C6, is obtained by adding as many as 6n−1 cycle C6 on the outer path of HCn−1. Figure 2 demonstrates hexagonal cluster graphs HC2, HC3, and HC4.Figure 2
Hexagonal cluster graphsHC2, HC3, and HC4.Some interconnection networks are designed, and some are borrowed from nature. For example, hypercubes, complete binary trees, butterflies, and torus networks are some of the designed architectures. Grids, hexagonal networks, honeycomb networks, and diamond networks, for instance, bear resemblance to atomic or molecular lattice structures. They are called natural architectures. The advancement of large scale integrated circuit technology has enabled the construction of complex interconnection networks. Besides that, the hexagonal cluster graphs have been studied as models of organic compounds build up entirely from benzene rings, social networks, and wireless sensor networks. Graph theory provides a fundamental tool for designing and analyzing such networks [7–11].In [2], Baca et al. studied the lower bound of tvsG for any graph G as follows.Theorem 1.
Ifp is the number of vertices of any graph G, δ is the minimum degree of vertex, and Δ is the maximum degree of vertex of G, then(1)tvsG≥p+δΔ+1.


## 3. Results and Discussion

In this paper, we have proved that the total vertex irregularity strength of the hexagonal cluster graph (network) withn cluster is equal to its lower bound in Theorem 1.Theorem 2.
Forn≥2, we have(2)tvsHCn=3n2+12.Proof.
Since the number of vertices ofHCn is 6n2, the minimum degree of vertex is 2 and the maximum degree of vertex is 3; by using (1) in Theorem 1, we found that(3)tvsHCn≥3n2+12.
To find thattvsHCn≤3n2+1/2, we have to construct a vertex irregular total k−labeling on HCn where k=3n2+1/2 as follows.
Note that there aren layers in HCn. Layer i is denoted by Li. For illustration, in Figure 3, there are 3 layers in HC3.
InL1, there is an outer cycle C12n−6 of HCn which consists of 6n vertices of degree 2 denoted by xii=1,2,⋯,6n,6n−1 vertices of degree 3 denoted by yjj=1,2,⋯,6n−1, and 12n−6 edges denoted by ett=1,2,⋯,12n−6.
Now, consider all vertices and all edges in the outer cycleC12n−6 of HCn sequentially.
To label some of vertices and all edges inL1, we use Algorithm 1 as follows.
To label all of edges inLt for 2≤t≤n−1 and for 3≤i≤2n−3 define(4)Si=6ni−32i2−1,foriis odd,(5)Si=6ni−32i2,foriis even,and use Algorithm 2 as follows.
All of edges ofHCn are already labeled, but vertices have not labeled yet. Next, label all of vertices using the following method. The temporary weight of a vertex x is the number of label of all edges incident tox, denoted by wx. For example, the temporary weight of a vertex x in Figure 4 is 8.
Order the temporary weight of all vertices and rename them byz1,z2,⋯,z6n2 such that 2=wx2=wz1≤wz2≤⋯≤wz6n2. For i=2,3,⋯,6n, define(6)fzi=max1,wtzi−1+1−wzi,wtzi=wzi+fzi,where wtz1=3 is the total weight of vertex z1.
Based on equation (6), we have that(7)the weights of all vertices inEHCnare distinct.
Besides that, from Algorithms1 and 2, we can see that(8)the largest label on HCnis3n2+12.
Based on Statements (7) and (8), we conclude that the function construction with Algorithms 1 and 2 is a total vertex irregular k−labeling on HCn where k=3n2+1/2. This shown as follows:(9)tvsHCn≤3n2+12.
Based on equations (3) and (9), we find equation (2), i.e., tvsHCn=3n2+1/2.
As illustration, we shall use Algorithms1 and 2 to construct a total vertex irregular 25-labeling on HC4. The first step, all the vertices and all the edges on the outer cyrcle C42 of HC4 are named sequentially as in Figure 5.
Now, we use Algorithm3 to label some of vertices and all edges in L1 as follows.
For3≤I≤5, using equations (4) and (5), we have S3=24.3–3/232−1=60,S4=24.4–3/242=72, and S5=24.5−3/252−1=84.
Then, use Algorithm4 to label all edges in L2 and L3, as follows.Figure 3
Hexagonal cluster graphsHC3 with their layers L1, L2, and L3.Algorithm 1:Algorithm for labeling all edges of the outer cycle of L1.
Step 1. For i=1+3k−1 where k=1,2,⋯,2n, label e′, e″, and xi with i+2/3 where e′ and e″ are edges incident to vertex xiStep 2. For i=1+3k−1 where k=1,2,⋯,2n, label edges between xi and xi+1by fxi+1 except for the labeling edges in Step 1Step 3. Label all edges between x1 and x6n−2 by fx6n−2+1=2n+1Step 4. Label the remaining edges of L1 by 4n−3Algorithm 2: Algorithm for labeling all other edges in HC(n).
K2t−1=(S2t−1+2−K2t−2)/3,
Step A. Label all of edges of the outer cycle in Lt for 2≤t≤n−1 by where K2=4n−3Step B. Label all of the remaining edges from Lt for 2≤t≤n−2 by K2t=S2t+2−2K2t−1/2Step C. Label all of the remaining edges in HCn by 3n2+1/2Figure 4
The temporary weight ofx is 8.Figure 5
The name of elements of the outer cycleC42 of L1 in HC4.Algorithm 3: Algorithm for labeling all edges of the outer cycle of L1 of HC(4).
Step 1. For i=1+3k−1 where k=1,2,3,4,5,6,7,8, label e′, e″, and xi with i+2/3 where e′ and e″ are edges incident to vertex xi (see Figure 6)Step 2. For i=1+3k−1 where k=1,2,3,4,5,6,7,8, label edges between xi and xi+1 by fxi+1 except for the labeling edges in Step 1Step 3. Label all edges between x1 and x22 by fx24+1=9 except for the labeling edges in Step 1 (see Figure 7)Step 4. Label the remaining edges of L1 by 13 (see Figure 8)Figure 6
The labels of some vertices and edges ofL1 in HC4.Figure 7
The labels of some vertices and edges ofL1 in HC4.Figure 8
The labels of some vertices and edges ofL1 in HC4.Algorithm 4: Algorithm for labeling all other edges in HC(4).
Step A. Label all edges of the outer cycle in L2 by using Algorithm 2, i.e., K3=S3+2−K2/3 where K2=13,i.e., K3=60+2−13/3=17 (see Figure 9) and all edges of the outer cycle in L3 by K5=S5+2−K4/3=84+2−20/3=22 (see Figure 10)Step B. Label all of the remaining edges from L2 by using Algorithm 2, i.e., K4=S4+2−2K3/2=72+2−2.17/2=20 (see Figure 11)Step C. Label all of the remaining edges in HC4 by 3.42+1/2=25 (see Figure 12)Figure 9
The labels of all edges of the outer cycleC30 of L2 in HC4.Figure 10
The labels of all edges of the outer cycleC18 of L3 in HC4.Figure 11
Layer 2 with edge labels.Figure 12
Layer 4 with edge labels.


## 4. Conclusions

In this paper, we obtained the precise values for the total vertex irregularity strength of the hexagonal cluster graphsHCn, for all n≥2. Furthermore, we show that the hexagonal cluster graphs HCn is an example that the lower bound in \cite{BJMR07} is sharp. In the future, we are interested in computing the exact value for the total vertex (or edge) irregularity strength of grids, hexagonal networks, and honeycombs networks.



---

*Source: 2743858-2021-01-23.xml*