On Total Vertex Irregularity Strength of Hexagonal Cluster Graphs

Abstract

For a simple graph $G$ with a vertex set $VG$ and an edge set $EG$, a labeling $f:VG{{\displaystyle \cup }}^{\text{}}EG⟶\mathrm{1,2},\cdots ,k$ is called a vertex irregular total $k-\text{labeling}$ of $G$ if for any two different vertices $x$ and $y$ in $VG$ we have $wtx\ne wty$ where $wtx=fx+{\displaystyle {\sum }_{u\in VG}fxu}.$ The smallest positive integer $k$ such that $G$ has a vertex irregular total $k-\text{labeling}$ is called the total vertex irregularity strength of $G$, denoted by $\text{tvs}G$. The lower bound of $\text{tvs}G$ 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\ge 2$. Moreover, we show that the total vertex irregularity strength of the hexagonal cluster graph on $n$ cluster is $3n^2+1/2$.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

A graph labeling is an assignment of integers from 1 to $n$, 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 graph $G$ 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{{\displaystyle \cup }}^{\text{}}EG$, then we call the labeling a total labeling.

A labeling $f:EG⟶1,2,3,\cdots ,k$ is called an edge $k-labeling$ of $G$. The associated vertex weight of a vertex $x\in VG$ under an edge $k-\text{labeling}$$f$ is defined as $wtx={\displaystyle {\sum }_{v\in Nx}fxv}$. Chartrand et al. [1] introduced an edge $k-\text{labeling}$ of a graph $G$ such that $wtx\ne wty$ for all vertices $x,y\in VG$ with $x\ne 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\prime$ by replacing each edge by a set of at most $k$ parallel edges, such that the degrees of the vertices in $G\prime$ are all different.

In this paper, we consider for a total $k-\text{labeling}$ of $G$, that is, $f:VG{{\displaystyle \cup }}^{\text{}}EG⟶1,2,3,\cdots ,k$. The associated vertex weight of a vertex $x\in VG$ under a total $k-\text{labeling}$$f$ is defined as $wtx=fx+{\displaystyle {\sum }_{v\in Nx}fxv}$. A total $k-\text{labeling}$$f$ is defined to be a vertex irregular total $k-labeling$ of $G$ if for every two different vertices $x$ and $y$ of $G$, $wtx\ne wty$. The minimum positive integer $k$ for which $G$ has a vertex irregular total $k-\text{labeling}$ is called the total vertex irregularity strength of $G$, denoted by $\text{tvs}G$. In Figure 1, there are a two total labeling of $P_4$, one of is a vertex irregular total 3-labeling of $P_4$ and the other is a vertex irregular total 2-labeling of $P_4$. However, $P_4$ does not have a vertex irregular total vertex 1-labeling. Such that the minimum positive integer $k$ for which $P_4$ has a vertex irregular total $k-\text{labeling}$ is 2, or the total vertex irregularity strength of $P_4$ is 2.

[figures omitted; refer to PDF]

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 with $n$ cluster for $n\ne 2$.

2. Hexagonal Cluster Graph

In this section, we give the definition of hexagonal cluster graphs. The hexagonal cluster graph with $n\ge 2$ cluster, denoted by $\text{HC}n$, where $\text{HC}1$ isomorphs to $C_6$, is obtained by adding as many as $6n-1$ cycle $C_6$ on the outer path of $\text{HC}n-1$. Figure 2 demonstrates hexagonal cluster graphs $\text{HC}2$, $\text{HC}3$, and $\text{HC}4$.

[figure omitted; refer to PDF]

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 $\text{tvs}G$ for any graph $G$ as follows.

Theorem 1.

If $p$ is the number of vertices of any graph $G$, $\delta$ is the minimum degree of vertex, and $\mathrm{\Delta }$ is the maximum degree of vertex of $G$, then$$\begin{array}{}\text{(1)}& \text{tvs}G\ge \frac{p+\delta }{\Delta +1}.\end{array}$$

3. Results and Discussion

In this paper, we have proved that the total vertex irregularity strength of the hexagonal cluster graph (network) with $n$ cluster is equal to its lower bound in Theorem 1.

Theorem 2.

For $n\ge 2$, we have$$\begin{array}{}\text{(2)}& \text{tvs}\text{HC}n=\frac{3n^2+1}{2}.\end{array}$$

Proof.

Since the number of vertices of $\text{HC}n$ is $6n^2$, the minimum degree of vertex is 2 and the maximum degree of vertex is 3; by using (1) in Theorem 1, we found that$$\begin{array}{}\text{(3)}& \text{tvs}\text{HC}n\ge \frac{3n^2+1}{2}.\end{array}$$

To find that $\text{tvs}\text{HC}n\le 3n^2+1/2$, we have to construct a vertex irregular total $k-\text{labeling}$ on $\text{HC}n$ where $k=3n^2+1/2$ as follows.

Note that there are $n$ layers in $\text{HC}n$. Layer $i$ is denoted by $L_i$. For illustration, in Figure 3, there are 3 layers in $\text{HC}3$.

In $L_1$, there is an outer cycle $C_{12n-6}$ of $\text{HC}n$ which consists of $6n$ vertices of degree 2 denoted by $x_{i}i=1,2,\cdots ,6n,$$6n-1$ vertices of degree 3 denoted by $y_{j}j=1,2,\cdots ,6n-1$, and $12n-6$ edges denoted by $e_{t}t=1,2,\cdots ,12n-6.$

Now, consider all vertices and all edges in the outer cycle $C_{12n-6}$ of $\text{HC}n$ sequentially.

To label some of vertices and all edges in $L_1,$ we use Algorithm 1 as follows.

To label all of edges in $L_t$ for $2\le t\le n-1$ and for $3\le i\le 2n-3$ define$$\begin{array}{}\text{(4)}& S_i=6ni-\frac{3}{2}{i}^2-1,\hspace{1em}\text{for\hspace{0.17em}}i\text{\hspace{0.17em}is\hspace{0.17em}odd},\text{(5)}& S_i=6ni-\frac{3}{2}{i}^2,\hspace{1em}\text{for\hspace{0.17em}}i\text{\hspace{0.17em}is\hspace{0.17em}even},\end{array}$$and use Algorithm 2 as follows.

All of edges of $\text{HC}n$ 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 to$x$, 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 by $z_1,z_2,\cdots ,z_{6n^2}$ such that $2=w{x}_2=w{z}_1\le w{z}_2\le \cdots \le w{z}_{6n^2}.$ For $i=2,3,\cdots ,6n$, define$$\begin{array}{c}\text{(6)}& f{z}_i=\max 1,wt{z}_{i-1}+1-w{z}_i,wt{z}_i=w{z}_i+f{z}_i,\end{array}$$where $wt{z}_1=3$ is the total weight of vertex $z_1$.

Based on equation (6), we have that$$\begin{array}{}\text{(7)}& \text{the\hspace{0.17em}weights\hspace{0.17em}of\hspace{0.17em}all\hspace{0.17em}vertices\hspace{0.17em}in}\mathrm{\hspace{0.17em}E}\text{HC}n\text{\hspace{0.17em}are\hspace{0.17em}distinct}\text{.}\end{array}$$

Besides that, from Algorithms 1 and 2, we can see that$$\begin{array}{}\text{(8)}& \text{the\hspace{0.17em}largest\hspace{0.17em}label\hspace{0.17em}on\hspace{0.17em}HC}nis\frac{3n^2+1}{2}.\end{array}$$

Based on Statements (7) and (8), we conclude that the function construction with Algorithms 1 and 2 is a total vertex irregular $k-\text{labeling}$ on $\text{HC}n$ where $k=3n^2+1/2$. This shown as follows:$$\begin{array}{}\text{(9)}& \text{tvs}\text{HC}n\le \frac{3n^2+1}{2}.\end{array}$$

Based on equations (3) and (9), we find equation (2), i.e., $\text{tvs}\text{HC}n=3n^2+1/2.$

As illustration, we shall use Algorithms 1 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 $C_{42}$ of $HC4$ are named sequentially as in Figure 5.

Now, we use Algorithm 3 to label some of vertices and all edges in $L_1$ as follows.

For $3\le \text{\hspace{0.17em}I\hspace{0.17em}}\le 5$, using equations (4) and (5), we have $S_3=24.3–3/23^2-1=60,$$S_4=24.4–3/24^2=72,$ and $S_5=24.5-3/25^2-1=84$.

Then, use Algorithm 4 to label all edges in $L_2$ and $L_3$, as follows.

[figure omitted; refer to PDF]

Algorithm 1: Algorithm for labeling all edges of the outer cycle of L1.

  Step 1. For $i=1+3k-1$ where $k=1,2,\cdots ,2n$, label $e^{\prime }$, $e^{″}$, and $x_i$ with $i+2/3$ where $e^{\prime }$ and $e^{″}$ are edges incident to vertex $x_i$

  Step 2. For $i=1+3k-1$ where $k=1,2,\cdots ,2n$, label edges between $x_i$ and $x_{i+1}$by $f{x}_i+1$ except for the labeling edges in Step 1

  Step 3. Label all edges between $x_1$ and $x_{6n-2}$ by $f{x}_{6n-2}+1=2n+1$

  Step 4. Label the remaining edges of $L_1$ by $4n-3$

Algorithm 2: Algorithm for labeling all other edges in HC(n).

  K_2t−1=(S_2t−1+2−K_2t−2)/3,  Step A. Label all of edges of the outer cycle in $L_t$ for $2\le t\le n-1$ by where $K_2=4n-3$

  Step B. Label all of the remaining edges from $L_t$ for $2\le t\le n-2$ by $K_{2t}=S_{2t}+2-2K_{2t-1}/2$

  Step C. Label all of the remaining edges in $\text{HC}n$ by $3n^2+1/2$

[figure omitted; refer to PDF][figure omitted; refer to PDF]

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^{\prime }$, $e^{″}$, and $x_i$ with $i+2/3$ where $e^{\prime }$ and $e^{″}$ are edges incident to vertex $x_i$ (see Figure 6)

  Step 2. For $i=1+3k-1$ where $k=1,2,3,4,5,6,7,8$, label edges between $x_i$ and $x_{i+1}$ by $f{x}_i+1$ except for the labeling edges in Step 1

  Step 3. Label all edges between $x_1$ and $x_{22}$ by $f{x}_{24}+1=9$ except for the labeling edges in Step 1 (see Figure 7)

  Step 4. Label the remaining edges of $L_1$ by 13 (see Figure 8)

[figure omitted; refer to PDF][figure omitted; refer to PDF][figure omitted; refer to PDF]

Algorithm 4: Algorithm for labeling all other edges in HC(4).

  Step A. Label all edges of the outer cycle in ${\text{L}}_2$ by using Algorithm 2, i.e., $K_3=S_3+2-K_2/3$ where $K_2=13,$i.e., $K_3=60+2-13/3=17$ (see Figure 9) and all edges of the outer cycle in $L_3$ by $K_5=S_5+2-K_4/3=84+2-20/3=22$ (see Figure 10)

  Step B. Label all of the remaining edges from $L_2$ by using Algorithm 2, i.e., $K_4=S_4+2-2K_3/2=72+2-2.17/2=20$ (see Figure 11)

  Step C. Label all of the remaining edges in $\text{HC}4$ by ${3.4}^2+1/2=25$ (see Figure 12)

[figure omitted; refer to PDF][figure omitted; refer to PDF][figure omitted; refer to PDF][figure omitted; refer to PDF]

4. Conclusions

In this paper, we obtained the precise values for the total vertex irregularity strength of the hexagonal cluster graphs $\text{HC}n$, for all $\text{n}\ge 2.$ Furthermore, we show that the hexagonal cluster graphs $\text{HC}n$ 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.

Acknowledgments

This research was supported by the Basic Science Research Program, National Research Foundation of Korea, Ministry of Education, (NRF-2018R1D1A1B07049584) and Basic Research Superior College, Directorate of Research and Community Service, Ministry of Research, Technology and Higher Education, Republic of Indonesia (007/SP2H/AMD/LT/DRPM/2020).

References

[1] G. Chartrand, M. S. Jacobson, J. Lehel, "Irregular networks," Congressus Numerantium, vol. 81, pp. 113-119, 1988.

[2] M. Baca, S. Jendrol, M. Miller, J. Ryan, "On irregular total labellings," Discrete Mathematics, vol. 307, pp. 1378-1388, 2007.

[3] Nurdin, A. N. M. Salman, N. N. Gaos, E. T. Baskoro, "On the total vertex-irregular strength of a disjoint union of t copies of a path," Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 71, pp. 227-233, 2009.

[4] E. T. B. Nurdin, A. N. M. Salman, N. N. Gaos, "On the total vertex irregularity strength of trees," Discrete Mathematics, vol. 71, pp. 227-233, 2010.

[5] Nurdin, M. Zakir, Firman, "Vertex-irregular labeling and vertex-irregular total labeling on caterpillar graph," International Journal of Applied Mathematics and Statistics, vol. 40 no. 10, pp. 99-105, 2013.

[6] Nurdin, H. K. Kim, "Irregular labeling on transportation network of splitting graphs of stars," Proceedings of the Jangjeon Mathematical Society, vol. 22 no. 1, pp. 103-108, 2019.

[7] O. Al-Mushayt, A. Ahmad, "On the total edge irregularity strength of hexagonal grid graphs," Australasian Journal of Combinatorics, vol. 53, pp. 263-271, 2012.

[8] I. Rajasingh, S. T. Arockiamary, "Total edge irregularity strength of honeycomb torus networks," Global Journal of Pure and Applied Mathematics, vol. 13 no. 4, pp. 1135-1142, 2017.

[9] J. Sedlacek, "Problem 27 in thoery of graphs and its applications," Proceedings of the Symposium Smolenice, pp. 163-167, 1963.

[10] I. Stojmenovic, "Honeycomb networks: topological properties and communication algorithms," IEEE Transactions on Parallel and Distributed Systems, vol. 8 no. 10, pp. 1036-1042, DOI: 10.1109/71.629486, 1997.

[11] I. Tarawneh, R. Hasni, A. Ahmad, "On the edge irregularity strength of grid graphs," AKCE International Journal of Graphs and Combinatorics, vol. 17 no. 1, pp. 414-418, DOI: 10.1016/j.akcej.2018.06.011, 2020.