Contents

On edge irregularity strength of some classes of Toeplitz graphs

Author(s): Noha Mohammad Seyam1, Muhammad Faisal Nadeem2
1College of Applied Sciences Mathematical Sciences Department, Umm Al-Qura University, Makkah Saudi Arabia
2Department of Mathematics, COMSATS University Islamabad Lahore Campus, Lahore 54000 Pakistan
Copyright © Noha Mohammad Seyam, Muhammad Faisal Nadeem. 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.

Abstract

An edge irregular \(k\)-labeling of a graph \(G\) is a labeling of vertices of \(G\) with labels from the set \(\{1,2,3,\dots,k\}\) such that no two edges of \(G\) have same weight. The least value of \(k\) for which a graph \(G\) has an edge irregular \(k\)-labeling is called the edge irregularity strength of \(G\). Ahmad et. al. [1] showed the edge irregularity strength of some particular classes of Toeplitz graphs. In this paper we generalize those results and finds the exact values of the edge irregularity strength for some generalize classes of Toeplitz graphs.

Keywords: irregular assignment; irregularity strength; edge irregularity strength; Toeplitz graph

1. Introduction and preliminaries

For various classes of graphs in the order to determine whether or not the certain type of a graph labelling exists, there is no polynomial time bounded algorithm is found in the literature of graph labellings. Thus, the problem of finding whether a specific classes of graphs posses a particular labeling is still extensively open. Labeling a graph is a one-to-one mapping that takes set of graph objects (vertex and edge) onto a set of numbers, called labels. Most of the graph labelling techniques traces their beginning to one defined by Rosa [2] in 1967 or one introduced by Graham et. al 1980 [3]. In the past 50 years, more than two hundred graph labeling techniques have been studied in more than two thousand papers. The idea of labelling a graph attained a lot of popularity in the field of combinatorial graph theory, this gained reputation is not only because of the challenges face while solving the problems of graph labelling but also because of their enormous applications in many other branches of science, for example, radar, missile guidance, networking, crystallography, code writing, cryptography (secret sharing schemes), data base management, astronomy, and in the design of circuits. Graph labeling is one of the fast growing research areas. New results are being discovered and published at a rapidly increasing rate [4]. There are massive number of problems and conjectures which are still unsolved in graph labeling. By a graph labeling we mean an assignment of numbers (usually positive integers) to a set of graph elements (vertices, edges, faces) subject to certain conditions, assigned numbers are called labels.
In 1988, Chartand et al.[5] defined vertex irregular labeling of a graph \(G\) (without isolated vertices) as an assignment of positive integers to the edges of \(G\) with the condition that no two distinct vertices have same weight where weights of vertices are defined as the sum of the assigned labels to the edges at each vertex. The minimum of the largest weight of an edge over all irregular assignments is called the irregularity strength \(s(G)\) of \(G\). If no such weight exists, \(s\left( G\right) =\infty\). Let \(G\) be a graph with the vertex set \(V\) and the edge set \(E\). A vertex \(k\)-labeling \(\phi : V(G)\longrightarrow \{1,2,3,\dots,k\}\) is called an edge irregular \(k\)-labeling if for any \(e,f\in E\left( G\right)\) with \(e\neq f,\) we have \(w_{\phi }\left( e\right) \neq w_{\phi }\left( f\right)\), where weight of an edge \(e=xy\in E\left( G\right)\) is \(w_{\phi }\left( e\right) =\phi \left( x\right) +\phi \left( y\right).\) The least integer \(k\) for which the graph \(G\) has an edge irregular \(k\)-labeling is called the edge irregularity strength of \(G\) and is denoted by \(es(G).\) Motivated by the paper on irregular labeling [5] various types of irregular labelings are defined for details and results see [6-15]. Irregular labeling in graph theory involves assigning distinct labels to graph elements under specific constraints, resulting in unique weights for vertices or edges. Various types include product-irregular labeling, where the product of labels of incident edges at each vertex is unique [16], and edge-irregular labeling, where the sum of labels of incident vertices for each edge is unique [17]. Distance irregular labeling ensures the sum of labels of vertices adjacent to each vertex is unique [18], while total irregularity strength involves unique sums of labels of vertices and edges incident to each vertex [19]. Modular irregular labeling uses sums modulo the number of vertices [20], and vertex-antimagic total labeling follows arithmetic progression rules [21]. Edge-irregular reflexive labeling ensures unique weights for each edge [22], while inclusive distance vertex irregular labeling focuses on unique sums in closed neighborhoods [23]. Finally, face irregular labeling applies to plane graphs, ensuring unique sums of vertices, edges, and faces [24].
Ahmad et al, in [25] introduced edge irregularity strength as a modification of an irregular assignment defined in [5].

In [25], along with the exact values of edge irregularity strength for path graph \(P_{n},\) star graph \(K_{1,n}\), \(n\geq 1\), double star graph \(S_{m,n}\), \(3\leq m\leq n\) and Cartesian product graph \(P_{n}\times P_{m},\) a result about the lower bound of the edge irregularity strength of a graph \(G\) is also given.

Theorem 1. [25] Let \(G\) be a simple graph with maximum degree \(\Delta =\Delta \left( G\right)\). Then \(es\left( G\right) \geq \max \left\{ \left\lceil \left( \left\vert E\left( G\right) \right\vert +1\right) /2\right\rceil ,\Delta \left( G\right) \right\}\).

Toeplitz graphs were introduced by Sierksma and since then this class of graphs is being investigated for different graph properties such as connectivity, planarity, hamiltonicity, bipartitness and colourability. A simple undirected graph is called a Toeplitz graph if its adjacency matrix is Toeplitz. For definition and properties of a Toeplitz graph see [26]. Here, we are considering only the definition of Toeplitz graph:

Let \(t_{1}<t_{2}\dots<t_{k}\leq n-1\) be a sequence of positive integers. The Toeplitz graph \(T=T_{n}\left\langle t_{1},t_{2},…,t_{k}\right\rangle\) is a graph with vertex set \(\left\{ v_{i}:i=1,2,…,n\right\}\), where the vertices \(v_{i}\) and \(v_{j}\) are adjacent when \(\left\vert v_{i}-v_{j}\right\vert =t_{l}\), for some \(l=1,2,…,k\). See [26] for detail of Toeplitz graphs.

The reader can easily verify that a Toeplitz graph is not necessarily connected. In this regard consider following result given in [26]:

Theorem 2. \(T_{n}\left\langle t_{1},t_{2},\dots,t_{k}\right\rangle\) has at least \(\gcd \left( t_{1},t_{2},\dots,t_{k}\right)\) connected components.

In [1], Ahmad et.al determined the exact values of the edge irregularity strength of \(T_{n}\left\langle 1,2\right\rangle\), \(T_{n}\left\langle 1,3\right\rangle\), \(T_{n}\left\langle 2,4\right\rangle\) and \(T_{n}\left\langle 1,2,3\right\rangle\) Toeplitz graphs. In this paper we extend those results and finds the exact values of the edge irregularity strength of \(T_{n} \langle 3,6\rangle\), \(T_{n} \langle 4,8\rangle,\) \(T_{n} \langle 5,10\rangle\) and \(T_{n} \langle 6,12\rangle\) of Toeplitz graphs.

2. Main Results

Theorem 3. Let \(T_n\langle 3,6\rangle\) be the Toeplitz graph with at least \(9\) vertices. Then \(es(T_n\langle 3,6\rangle)= n-2\).

Proof. Let \(T_n\langle 3,6\rangle\) is a Toeplitz graph by the addition of vertex set \(V(T_n\langle 3,6\rangle)=\{r_j: 1 \le j \le n \}\) and the edge set \(E(T_n\langle 3,6\rangle)=\{r_jr_{j+3}: 1 \le j \le n-3 \}\cup \{r_jr_{j+6}: 1 \le j \le n-6 \}\). Keeping in view the lower bound theorem, there is \(es(T_n\langle 3,6\rangle) \ge n-2\). The process of conversion, it will be described as an appropriate edge irregular labeling \(\varphi: V(T_n\langle 3,6\rangle) \to \{ 1,2, \dots, n-2\}\) be the vertex labeling such that

\[\varphi(r_j)=\left\{ \begin{array}{ll} \frac{j+2}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod3\\[2mm] \left\lceil \frac{n+j-2}{3}\right\rceil, & \mathrm {if}\ \ j\equiv 2 \pmod3\\[2mm] \left\lceil \frac{2n+j-6}{3}\right\rceil,& \mathrm {if}\ \ j\equiv 0 \pmod3\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+3})\) are as follows

For \(n\equiv 1 \pmod3\) the weights are given below,

\[w_{\varphi}(r_jr_{j+3})= \left\{ \begin{array}{ll} \frac{2j+7}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod3\\[2mm] \frac{2n+2j+3}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod3\\[2mm] \frac{4n+2j-7}{3}, & \mathrm{if}\ \ j\equiv 0 \pmod3\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod3\) the weights are given below, \[w_{\varphi}(r_jr_{j+3})= \left\{ \begin{array}{ll} \frac{2j+7}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod3\\[2mm] \frac{2n+2j+1}{3}, &\mathrm {if}\ \ j\equiv 2 \pmod3\\[2mm] \frac{4n+2j-5}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod3\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod3\) the weights are given below,

\[w_{\varphi}(r_jr_{j+3})= \left\{ \begin{array}{ll} \frac{2j+7}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod3\\[2mm] \frac{2n+2j-1}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod3\\[2mm] \frac{4n+2j-9}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod3\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+6})\) are as follows

For \(n\equiv 1 \pmod3\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{2j+10}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod3\\[2mm] \frac{2n+2j+6}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod3\\[2mm] \frac{4n+2j-4}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod3\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod3\) the weights are given below, \[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{2j+10}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod3\\[2mm] \frac{2n+2j+4}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod3\\[2mm] \frac{4n+2j-2}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod3\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod3\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{2j+10}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod3\\[2mm] \frac{2n+2j+2}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod3\\[2mm] \frac{4n+2j-6}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod3\\[2mm] \end{array} \right.\]

As the edge weights are distinct in the sense of all its pairs of distinct edges, as the vertex labeling \(\varphi\) is appropriate edge irregular \((n-2)\)-labeling. Therefore, \(es(T_n\langle 3,6\rangle)= n-2\). ◻

Theorem 4. Let \(T_n\langle 4,8\rangle\) be the Toeplitz graph with at least \(12\) vertices. Then \(es(T_n\langle 4,8\rangle)= n-3\).

Proof. Let \(T_n\langle 4,8\rangle\) is a Toeplitz graph by the addition of vertex set \(V(T_n\langle 4,8\rangle)=\{r_j: 1 \le j \le n \}\) and the edge set \(E(T_n\langle 3,6\rangle)=\{r_jr_{j+4}: 1 \le j \le n-4 \}\cup \{r_jr_{j+8}: 1 \le j \le n-8 \}\). Keeping in view the lower bound theorem, there is \(es(T_n\langle 4,8\rangle) \ge n-3\). The process of conversion, it will be described as an appropriate edge irregular labeling \(\varphi: V(T_n\langle 4,8\rangle) \to \{ 1,2, \dots, n-3\}\) be the vertex labeling such that

\[\varphi(r_j)=\left\{ \begin{array}{ll} \frac{j+3}{4}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \left\lceil \frac{n+j-2}{4}\right\rceil, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \left\lceil \frac{2n+j-6}{4}\right\rceil, & \mathrm {if}\ \ j\equiv 3 \pmod4\,\, {\mathrm and }\ \,\, n\equiv 1,2,3 \pmod4\\[2mm] \frac{2n+j-7}{4}, & \mathrm {if}\ \ j\equiv 3 \pmod4\,\, {\mathrm and }\ \,\, n\equiv 0 \pmod4\\[2mm] \left\lceil \frac{2n+j-6}{3}\right\rceil, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+4})\) are as follows

For \(n\equiv 1 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+4})= \left\{ \begin{array}{ll} \frac{j+5}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j+3}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j-3}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-9}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+4})= \left\{ \begin{array}{ll} \frac{j+5}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j+2}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j-1}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-8}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

For \(n\equiv 3 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+4})= \left\{ \begin{array}{ll} \frac{j+5}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j+1}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j-3}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-7}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+4})= \left\{ \begin{array}{ll} \frac{j+5}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j-5}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-10}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+8})\) are as follows

For \(n\equiv 1 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+8})= \left\{ \begin{array}{ll} \frac{j+7}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j+5}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j-1}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-7}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+8})= \left\{ \begin{array}{ll} \frac{j+7}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j+4}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j+1}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-6}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

For \(n\equiv 3 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+8})= \left\{ \begin{array}{ll} \frac{j+7}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j+3}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j-1}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-5}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod4\) the weights are given below,

\[w_{\varphi}(r_jr_{j+8})= \left\{ \begin{array}{ll} \frac{j+7}{2}, & \mathrm {if}\ \ j\equiv 1 \pmod4\\[2mm] \frac{n+j+2}{2}, & \mathrm {if}\ \ j\equiv 2 \pmod4\\[2mm] \frac{2n+j-3}{2}, & \mathrm {if}\ \ j\equiv 3 \pmod4\\[2mm] \frac{3n+j-8}{2}, & \mathrm {if}\ \ j\equiv 0 \pmod4\\[2mm] \end{array} \right.\]

As the edge weights are distinct in the sense of all its pairs of distinct edges, as the vertex labeling \(\varphi\) is appropriate edge irregular \((n-3)\)-labeling. Therefore, \(es(T_n\langle 4,8\rangle)= n-3\). ◻

Theorem 5. Let \(T_n\langle 5,10\rangle\) be the Toeplitz graph with at least \(15\) vertices. Then \(es(T_n\langle 5,10\rangle)= n-4\).

Proof. Let \(T_n\langle 5,10\rangle\) is a Toeplitz graph by the addition of vertex set \(V(T_n\langle 5,10\rangle)=\{r_j: 1 \le j \le n \}\) and the edge set \(E(T_n\langle 5,10\rangle)=\{r_jr_{j+5}: 1 \le j \le n-5 \}\cup \{r_jr_{j+10}: 1 \le j \le n-10 \}\). Keeping in view the lower bound theorem, there is \(es(T_n\langle 5,10\rangle) \ge n-4\). The process of conversion, it will be described as an appropriate edge irregular labeling \(\varphi: V(T_n\langle 5,10\rangle) \to \{ 1,2, \dots, n-4\}\) be the vertex labeling such that

\[\varphi(r_j)=\left\{ \begin{array}{ll} \frac{j+4}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \left\lceil \frac{n+j-2}{5}\right\rceil, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \left\lceil \frac{2n+j-6}{5}\right\rceil, & \mathrm {if}\ \ j\equiv 3 \pmod5\,\, {\mathrm and }\ \,\, n\equiv 1,2,3,4 \pmod5\\[2mm] \frac{2n+j-8}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\,\, {\mathrm and }\ \,\, n\equiv 0 \pmod5\\[2mm] \left\lceil \frac{3n+j-12}{5}\right\rceil, & \mathrm {if}\ \ j\equiv 4 \pmod5\,\, {\mathrm and }\ \,\, n\equiv 1,2,3,4 \pmod5\\[2mm] \frac{3n+j-14}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\,\, {\mathrm and }\ \,\, n\equiv 0 \pmod5\\[2mm] \left\lceil \frac{4n+j-20}{5}\right\rceil, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+5})\) are as follows

For \(n\equiv 1 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+5})= \left\{ \begin{array}{ll} \frac{2j+13}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+9}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j-5}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-19}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-33}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+5})= \left\{ \begin{array}{ll} \frac{2j+13}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+7}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j+1}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-15}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-31}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 3 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+5})= \left\{ \begin{array}{ll} \frac{2j+13}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+5}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j-3}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-11}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-29}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 4 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+5})= \left\{ \begin{array}{ll} \frac{2j+13}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+3}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j-7}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-17}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-27}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+5})= \left\{ \begin{array}{ll} \frac{2j+13}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+1}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j-11}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-23}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-35}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+10})\) are as follows

For \(n\equiv 1 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+10})= \left\{ \begin{array}{ll} \frac{2j+18}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+14}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-14}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-28}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+10})= \left\{ \begin{array}{ll} \frac{2j+18}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+12}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j+6}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-10}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-26}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 3 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+10})= \left\{ \begin{array}{ll} \frac{2j+18}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+10}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j+2}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-6}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-24}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 4 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+10})= \left\{ \begin{array}{ll} \frac{2j+18}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+8}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j-2}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-12}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-22}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod5\) the weights are given below,

\[w_{\varphi}(r_jr_{j+10})= \left\{ \begin{array}{ll} \frac{2j+18}{5}, & \mathrm {if}\ \ j\equiv 1 \pmod5\\[2mm] \frac{2n+2j+6}{5}, & \mathrm {if}\ \ j\equiv 2 \pmod5\\[2mm] \frac{4n+2j-6}{5}, & \mathrm {if}\ \ j\equiv 3 \pmod5\\[2mm] \frac{6n+2j-18}{5}, & \mathrm {if}\ \ j\equiv 4 \pmod5\\[2mm] \frac{8n+2j-30}{5}, & \mathrm {if}\ \ j\equiv 0 \pmod5\\[2mm] \end{array} \right.\]

As the edge weights are distinct in the sense of all its pairs of distinct edges, as the vertex labeling \(\varphi\) is appropriate edge irregular \((n-4)\)-labeling. Therefore, \(es(T_n\langle 5,10\rangle)= n-4\). ◻

Theorem 6. Let \(T_n\langle 6,12\rangle\) be the Toeplitz graph with at least \(18\) vertices. Then \(es(T_n\langle 6,18\rangle)= n-5\).

Proof. Let \(T_n\langle 6,12\rangle\) is a Toeplitz graph by the addition of vertex set \(V(T_n\langle 6,12\rangle)=\{r_j: 1 \le j \le n \}\) and the edge set \(E(T_n\langle 6,12\rangle)=\{r_jr_{j+6}: 1 \le j \le n-6 \}\cup \{r_jr_{j+12}: 1 \le j \le n-12 \}\). Keeping in view the lower bound theorem, there is \(es(T_n\langle 6,12\rangle) \ge n-5\). The process of conversion, it will be described as an appropriate edge irregular labeling \(\varphi: V(T_n\langle 6,12\rangle) \to \{ 1,2, \dots, n-5\}\) be the vertex labeling such that

\[\varphi(r_j)=\left\{ \begin{array}{ll} \frac{j+5}{6}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \left\lceil \frac{n+j-2}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \left\lceil \frac{2n+j-6}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 3 \pmod6\,\, {\mathrm and }\ \,\, n\equiv 1,2,3,4 \pmod6\\[2mm] \left\lceil \frac{2n+j-9}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 3 \pmod6\,\, {\mathrm and }\ \,\, n\equiv 0,5 \pmod6\\[2mm] \left\lceil \frac{3n+j-12}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 4 \pmod6\,\, {\mathrm and }\ \,\, n\equiv 2,3,4 \pmod6\\[2mm] \left\lceil \frac{3n+j-16}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 4 \pmod6\,\, {\mathrm and }\ \,\, n\equiv 0,1,5 \pmod6\\[2mm] \left\lceil \frac{4n+j-20}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 5 \pmod6\,\, {\mathrm and }\ \,\, n\equiv 2,3,4 \pmod6\\[2mm] \left\lceil \frac{4n+j-24}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 5 \pmod6\,\, {\mathrm and }\ \,\, n\equiv 0,1,5 \pmod6\\[2mm] \left\lceil \frac{5n+j-30}{6}\right\rceil, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+6})\) are as follows

For \(n\equiv 1 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{j+8}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+6}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j-2}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-10}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-18}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-26}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{j+8}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+5}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j+2}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-7}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-16}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-25}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 3 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{j+8}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+4}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-4}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-14}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-24}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 4 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{j+8}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+3}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j-2}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-7}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-12}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-23}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 5 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{j+8}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+2}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j-4}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-10}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-16}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-22}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+6})= \left\{ \begin{array}{ll} \frac{j+8}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+1}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j-6}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-13}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-20}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-27}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

The edge weights for \(w_{\varphi}(r_jr_{j+12})\) are as follows

For \(n\equiv 1 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+12})= \left\{ \begin{array}{ll} \frac{j+11}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+9}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j+1}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-7}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-15}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-23}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 2 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+12})= \left\{ \begin{array}{ll} \frac{j+11}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+8}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j+5}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-4}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-13}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-22}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 3 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+12})= \left\{ \begin{array}{ll} \frac{j+11}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+7}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j+3}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-1}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-11}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-21}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 4 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+12})= \left\{ \begin{array}{ll} \frac{j+11}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+6}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j+1}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-4}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-9}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-20}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 5 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+12})= \left\{ \begin{array}{ll} \frac{j+11}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+5}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j-1}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-7}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-13}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-19}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\]

For \(n\equiv 0 \pmod6\) the weights are given below,

\[w_{\varphi}(r_jr_{j+12})= \left\{ \begin{array}{ll} \frac{j+11}{3}, & \mathrm {if}\ \ j\equiv 1 \pmod6\\[2mm] \frac{n+j+4}{3}, & \mathrm {if}\ \ j\equiv 2 \pmod6\\[2mm] \frac{2n+j-3}{3}, & \mathrm {if}\ \ j\equiv 3 \pmod6\\[2mm] \frac{3n+j-10}{3}, & \mathrm {if}\ \ j\equiv 4 \pmod6\\[2mm] \frac{4n+j-17}{3}, & \mathrm {if}\ \ j\equiv 5 \pmod6\\[2mm] \frac{5n+j-24}{3}, & \mathrm {if}\ \ j\equiv 0 \pmod6\\[2mm] \end{array} \right.\] As the edge weights are distinct in the sense of all its pairs of distinct edges, as the vertex labeling \(\varphi\) is appropriate edge irregular \((n-5)\)-labeling. Therefore, \(es(T_n\langle 6,10\rangle)= n-5\). ◻

3. Conclusions

In this paper, the existence of the irregular labeling and edge irregularity strength of Toeplitz graphs \(T_n\langle 3,6\rangle\), \(T_n\langle 4,8\rangle\), \(T_n\langle 5,10\rangle\) and \(T_n\langle 6,12\rangle\) is studied. Though there are the other research scholars who have made research papers on this topic, yet this work is unique in its significance and scope because no one has worked on it. We determined the labeling of above Toeplitz graphs which includes vertex labeling and edge labeling, and investigated the edge irregularity strength of Toeplitz graphs. We proved that \[es(T_n\langle 3,6\rangle)= n-2\] \[es(T_n\langle 4,8\rangle)= n-3\] \[es(T_n\langle 5,10\rangle)= n-4\] \[es(T_n\langle 6,12\rangle)= n-5\]

we believe that the value of edge irregularity strength of above Toeplitz graphs are exact and therefore these values are helpful to find the edge irregularity strength of others Toeplitz graphs. We propose the following open problems.

Open Problem 1. Determining the irregular labeling of Toeplitz graphs \((T_n\langle t_1,t_2\rangle)\) arbitrary \(t_1\) and \(t_2\). Similarly, how does varying \(t_i\) affect the irregular labeling and can a comprehensive characterization be developed?

References

  1. Ahmad, A., Bača, M., & Nadeem, M. F. (2016). On edge irregularity strength of Toeplitz graphs. UPB Scientific Bulletin, Series A: Applied Mathematics and Physics, 78(4), 155-162.
  2. Rosa, A. (1966, July). On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Symposium, Rome (pp. 349-355).
  3. Graham, R. L., & Sloane, N. J. A. (1980). On additive bases and harmonious graphs. SIAM Journal on Algebraic Discrete Methods, 1(4), 382-404.
  4. Gallian, J. A. (2018). A dynamic survey of graph labeling. Electronic Journal of combinatorics, 1(DynamicSurveys), DS6.
  5. Chartrand, G., Jacobson, M. S., Lehel, J., Oellermann, O. R., Ruiz, S., & Saba, F. (1988). Irregular networks. Congr. Numer, 64(197-210), 250th.
  6. Bača, M., Miller, M., & Ryan, J. (2007). On irregular total labellings. Discrete mathematics, 307(11-12), 1378-1388.
  7. Bohman, T., & Kravitz, D. (2004). On the irregularity strength of trees. Journal of graph theory, 45(4), 241-254.
  8. Marzuki, C. C., Salman, A. N. M., & Miller, M. (2013). On the total irregularity strength of cycles and paths. Far East journal of mathematical sciences, 82(1), 1.
  9. Frieze, A., Gould, R. J., Karoński, M., & Pfender, F. (2002). On graph irregularity strength. Journal of graph theory, 41(2), 120-137.
  10. Ivančo, J., & Jendrol, S. (2006). Total edge irregularity strength of trees. Discussiones mathematicae graph theory, 26(3), 449-456.

  11. PrzybyŁo, J. (2009). Linear bound on the irregularity strength and the total vertex irregularity strength of graphs. SIAM journal on discrete mathematics, 23(1), 511-516.
  12. Majerski, P., & Przybyło, J. (2014). Total vertex irregularity strength of dense graphs. Journal of graph theory, 76(1), 34-41.
  13. D. Zhao, Z. Iqbal, R. Irfan, M. A. Chaudhry, M. Ishaq, M .K. Jamil, Asfand Fahad, Comparison of irregularity indices of several dendrimers structures, Processes 2019, 7, 662; doi:10.3390/pr7100662.

  14. Majerski, P., & Przybyło, J. (2014). On irregularity strength of dense graphs. Journal of Graph Theory 28(1), 197-205.
  15. Kalkowski, M., Karoński, M., & Pfender, F. (2011). A new upper bound for the irregularity strength of graphs. SIAM journal on discrete mathematics, 25(3), 1319-1321.

  16. Anholcer, M. (2009). Product irregularity strength of graphs. Discrete Mathematics, 309, 6434-6439.

  17. Ahmad, A., Al-Mushayt, O., & Bača, M. (2014). On edge irregularity strength of graphs. Applied Mathematics and Computations, 243, 607-610.

  18. Susanto, F., Wijaya, K., Purnama, P. M., & Slamin, S. (2022). On Distance Irregular Labeling of Disconnected Graphs. Kragujevac Journal of Mathematics, 46(4), 507-523.

  19. Ramdani, R., Salman, A., & Assiyatun, H. (2015). On The Total Irregularity Strength of Regular Graphs. Journal of Mathematical and Fundamental Sciences, 47(3), 281-295.
  20. Sugeng, K. A., Barack, Z. Z., Hinding, N., & Simanjuntak, R. (2021). Modular irregular labeling on double-star and friendship graphs. Journal of Mathematics, 2021, Article ID 4746609.

  21. Bača, M., Bertault, F., MacDougall, J., Miller, M., & Simanjuntak, R. (2003). Vertex-antimagic total labelings of graphs. Discussiones Mathematicae Graph Theory, 23, 67-83.
  22. Agustin, I. H., Utoyo, I., Dafik, D., & Venkatachalam, M. (2020). Edge irregular reflexive labeling of some tree graphs. Journal of Physics: Conference Series, 1543(1), 012008.
  23. Bača, M., Semaničová-Feňovčíková, A., Slamin, S., & Sugeng, K. (2018). Inclusive distance vertex irregular labelings. Electronic Journal of Graph Theory and Applications, 6(1), 61-83.

  24. Bača, M., Ovais, A., Semaničová-Feňovčíková, A., & Suparta, I. N. (2020). On Face Irregular Evaluations of Plane Graphs.Discussiones Mathematicae Graph Theory, 42, 549-568.

  25. Ahmad, A., Al-Mushayt, O. B. S., & Bača, M. (2014). On edge irregularity strength of graphs. Applied mathematics and computation, 243, 607-610.
  26. van Dal, R., Tijssen, G., Tuza, Z., van der Veen, J. A., Zamfirescu, C., & Zamfirescu, T. (1996). Hamiltonian properties of Toeplitz graphs. Discrete Mathematics, 159(1-3), 69-81.