On total edge irregularity strength for some special types of uniform theta snake graphs

1.   Introduction

In graph theory, graph labeling is an assignment of labels or weights to the vertices and edges of a graph. Graph labeling plays an important role in many fields such as computer science, coding theory and physics ^[32]. Baca et al. ^[10] have introduced the definition of an edge irregular total $\ell$-labeling of any graph as a labeling $\mathcal{L}:V \cup E\to \left\{\mathrm{1, 2}, 3, \dots, \ell\right\}$ in which every two distinct edges $fh$ and ${f}^{*}{h}^{*}$ of a graph $G$ have distinct weights, this means that ${w}_{\mathcal{L}}\left(fh\right)\ne {w}_{\mathcal{L}}\left({f}^{*}{h}^{*}\right)$ where ${w}_{\mathcal{L}}\left(fh\right) = \mathcal{L}\left(f\right)+\mathcal{L}\left(h\right)+\mathcal{L}\left(fh\right)$. They have deduced inequality which gives a lower bound of $tes\left(G\right)$ for a graph $G$,

Also, they have introduced the exact value of TEIS, $tes\left(G\right)$ for some families of graphs like fan graph ${F}_{n}$ and wheel graph ${W}_{n}$,

In ^[15] authors have proved that for any tree $T$

where $\Delta$ is maximum degree on $k$ vertices. In addition, Salama ^[26] investigated the exact value of TEIS for a polar grid graph,

Authors in ^[1] determined $\mathrm{T}\mathrm{E}\mathrm{I}\mathrm{S}$ for zigzag graphs. Also, the exact value of TEIS of the generalized web graph ${W}_{n, m}$ and some families has been determined, see ^[14]. Tilukay et al. ^[31] have investigated total irregularity strength for a wheel graph, a fan graph, a triangular Book graph and a friendship graph. On the other hand, in ^{[2,3,8,17,20,24,29]} the total edge irregularity strengths for hexagonal grid graphs, centralized uniform theta graphs, generalized helm graph, series parallel graphs, disjoint union of isomorphic copies of generalized Petersen graph, disjoint union of wheel graphs, subdivision of star ${S}_{n}$ and categorical product of two cycles have been investigated. For more details, see ^{[4,5,6,7,9,11,12,13,16,18,19,21,23,25,27,28,30]}.

A generalized theta graph $\theta ({t}_{1}, {t}_{2}, \dots, {t}_{n})$ is a pair of $n$ internal disjoint paths with lengths at least two joined by end vertices where the end vertices are named south pole $S$ and north pole $N$ and ${t}_{i}$ is the number of vertices in the nth path. Uniform theta graph $\theta (t, m)$ is a generalized theta graph in which all paths have the same numbers of internal vertices, for more details see ^[22].

In this paper, we have defined a new type of family of graph called uniform theta snake graph, ${\theta }_{n}(t, m)$. Also, the exact value of TEIS for some special types of the new family has been determined.

2.   Main results

In the following, we define a new type of graph which is called uniform theta snake graph.

Definition 1. If we replace each edge of a path ${P}_{n}$ by a uniform theta graph $\theta (t, m)$, we have a uniform theta snake graph ${\theta }_{n}(t, m)$. See Figure 1.

It is clear that for a uniform theta snake graph $\left|\mathrm{E}\left({\mathtt{θ }}_{\mathrm{n}}\right(\mathrm{t}, \mathrm{m}\left)\right)\right| = \mathrm{t}\left(\mathrm{m}+1\right)\mathrm{n}$ and $\left|\mathrm{V}\left({\mathtt{θ }}_{\mathrm{n}}\right(\mathrm{t}, \mathrm{m}\left)\right)\right| = \left(\mathrm{t}\mathrm{m}+1\right)\mathrm{n}+1$. In this section, we determine the exact value of TEIS for uniform theta snake graph ${\mathtt{θ }}_{\mathrm{n}}\left(\mathrm{3, 3}\right)$, ${\mathtt{θ }}_{\mathrm{n}}\left(3, \mathrm{m}\right)$, ${\mathtt{θ }}_{\mathrm{n}}(\mathrm{t}, 3)$, ${\mathtt{θ }}_{\mathrm{n}}\left(4, \mathrm{m}\right)$, and ${\mathtt{θ }}_{\mathrm{n}}(\mathrm{t}, 4)$.

Theorem 1. For a uniform theta snake graph ${\theta }_{n}\left(\mathrm{3, 3}\right)$ with 10$n+1$ vertices and 12$n$ edges, we have

Proof. Since a uniform theta snake graph ${\theta }_{n}\left(\mathrm{3, 3}\right)$ has 12$n$ edges and $\left({\theta }_{n}\left(\mathrm{3, 3}\right)\right) = 6$, then from (1) we have:

To prove the invers inequality, we show that $ħ-$ labeling is an edge irregular total for ${\theta }_{n}\left(\mathrm{3, 3}\right)$, see Figure 2, and $ħ = 4n+1$. Let $ħ = 4n+1$ and a total $ħ-$ labeling $\alpha :V{(\theta }_{n}\left(\mathrm{3, 3}\right)) \cup E({\theta }_{n}\left(\mathrm{3, 3}\right))\to \left\{\mathrm{1, 2}, 3, \dots, \mathrm{ħ}\right\}$ is defined as:

It is clear that $ħ$ is the greatest used label. The weights of edges of ${\theta }_{n}\left(\mathrm{3, 3}\right)$ are given by:

Obviously, the weights of edges are distinct. So $\alpha$ is an edge irregular total $\mathrm{ħ}-$ labeling. Hence

Theorem 2. For ${\theta }_{n}\left(3, m\right), m>3$ be a uniform theta snake graph. Then

Proof. Since $\left|E\left({\theta }_{n}\right(3, m\left)\right)\right| = 3\left(m+1\right)n$ and $\Delta \left({\theta }_{n}\right(3, m\left)\right) = 6$. Substituting in (1), we find

The existence of an edge irregular total $ƛ-$ labeling for ${\theta }_{n}(3, m)$, See Figure 3, $m>3$ will be shown, with $ƛ = (m+1)n+1$. Define a total $ƛ-$ labeling $\beta :V\left({\theta }_{n}(3, m)\right)\cup E\left({\theta }_{n}(3, m)\right)\to \left\{\mathrm{1, 2}, 3, \dots, ƛ\right\}$ for ${\theta }_{n}(3, m)$ as:

Clearly, $ƛ$ is the most label of edges and vertices. The edges weights are given as follows:

It is obvious that the weights of edges are different, thus $\beta$ is an edge irregular total $ƛ-$ labeling of ${\theta }_{n}(3, m)$. Hence

Theorem 3. Let ${\theta }_{n}\left(t, 3\right)$ be a theta snake graph for $t>3$. Then

Proof. A size of the graph ${\theta }_{n}(t, 3)$ equals $4tn$ and $\Delta \left({\theta }_{n}\left(t, 3\right)\right) = 2t$, then from (1) we have

We define an edge irregular total $ħ-$ labeling for ${\theta }_{n}(t, 3)$ to get upper bound. So, let $ħ = \left\lceil {\frac{4tn+2}{3}} \right\rceil$ and a total $ħ-$ labeling $\gamma :V\left({\theta }_{n}(t, 3)\right)\cup E\left({\theta }_{n}(t, 3)\right)\to \left\{\mathrm{1, 2}, 3, \dots, ħ\right\}$ is defined in the following three cases:

Case 1. $4tn+2\equiv 0\left(mod \; 3\right)$

$\gamma$ is defined as:

Obviously, $ħ$ is the greatest label. The edges weights of ${\theta }_{n}(t, 3)$ can be expressed as:

It implies that the edges weights have distinct values. So $\gamma$ is the desired edge irregular total $ħ-$ labeling, $ħ = \left\lceil {\frac{4tn+2}{3}} \right\rceil$. Hence

Case 2. $4tn+2\equiv 1\left(mod \; 3\right)$

$\mathrm{D}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}\;\gamma$ as:

It is clear that the greatest label is $ħ$. We define the weights of edges of ${\theta }_{n}(t, 3)$ as:

It is obvious that the edges weights are different. Then

Case 3. $4tn+2\equiv 2\left(mod \; 3\right)$

$\gamma$ is defined as follows:

We can see that $ħ$ is the greatest label. For edges weights of ${\theta }_{n}(t, 3)$, we have

It clears that the edges weights are i distinct. So $\gamma$ is the desired edge irregular total $ħ-$ labeling, $ħ = \left\lceil {\frac{4tn+2}{3}} \right\rceil$. Hence

Theorem 4. For ${\theta }_{n}\left(4, m\right)$ be a theta snake graph for $t>3$. Then

Proof. Since $\left|E\left({\theta }_{n}\left(4, m\right)\right)\right| = 4(m+1)n$ and $\Delta \left({\theta }_{n}\left(4, m\right)\right) = 8$, then from (1) we have

The existence of an edge irregular total $ƛ-$ labeling for ${\theta }_{n}(4, m)$, $m>3$ will be shown, with $ƛ = \left\lceil {\frac{4(m+1)n+2}{3}} \right\rceil$. Define a total $ƛ-$ labeling $\beta :V\left({\theta }_{n}(4, m)\right)\cup E\left({\theta }_{n}(4, m)\right)\to \left\{\mathrm{1, 2}, 3, \dots, ƛ\right\}$ for ${\theta }_{n}(4, m)$ in the following three cases as:

Case 1. $4\left(m+1\right)n+2\equiv 0\left(mod \; 3\right)$, $i = 1, 2, \mathrm{3, 4}$

$\beta$ is defined as:

It is clear that $ƛ$ is the greatest used label. The weights of edges of ${\theta }_{n}(4, m)$ are given by:

It is obvious that the weights of edges are different, thus $\beta$ is an edge irregular total $ƛ-$ labeling of ${\theta }_{n}(4, m)$. Hence

Case 2. $4\left(m+1\right)n+2\equiv 1\left(mod \; 3\right)$, $i = 1, 2, \mathrm{3, 4}$

$\beta$ is defined as:

It is clear that $ƛ$ is the greatest used label. The weights of edges of ${\theta }_{n}(4, m)$ are given by:

It is obvious that the weights of edges are different, thus $\beta$ is an edge irregular total $ƛ-$ labeling of ${\theta }_{n}(4, m)$. Hence

Case 3. $4\left(m+1\right)n+2\equiv 2\left(mod \; 3\right)$, $i = 1, 2, \mathrm{3, 4}$

$\beta$ is defined as:

It is clear that $ƛ$ is the greatest used label. The weights of edges of ${\theta }_{n}(4, m)$ are given by:

It is obvious that the weights of edges are different, thus $\beta$ is an edge irregular total $ƛ-$ labeling of ${\theta }_{n}(4, m)$. Hence

Theorem 5. If ${\theta }_{n}\left(t, 4\right)$ is theta snake graph for $t>3$. Then

Proof. Since $\left|E\left({\theta }_{n}\right(t, 4\left)\right)\right| = 5tn$ and $\Delta \left({\theta }_{n}\right(t, 4\left)\right) = 2t$. Substituting in (1), we have

We define an edge irregular total $ħ-$ labeling for ${\theta }_{n}(t, 4)$ to get upper bound. Let $ħ = \left\lceil {\frac{5tn+2}{3}} \right\rceil$ and a total $ħ-$ labeling $\gamma :V\left({\theta }_{n}(t, 4)\right)\cup E\left({\theta }_{n}(t, 4)\right)\to \left\{\mathrm{1, 2}, 3, \dots, ħ\right\}$ is defined in the following three cases:

Case 1. $5tn+2\equiv 0\left(mod \; 3\right)$

$\mathrm{D}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}\; \gamma$ as:

It is clear that, $ħ$ is the greatest label. The edges weights of ${\theta }_{n}(t, 4)$ can be expressed as:

It implies that the edges weights have distinct values. So $\gamma$ is the desired edge irregular total $ħ-$ labeling, $ħ = \left\lceil {\frac{5tn+2}{3}} \right\rceil$. Hence

Case 2. $5tn+2\equiv 1\left(mod \; 3\right)$

$\mathrm{D}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}\; \gamma$ as:

It is clear that the i greatest label is $ħ$. We define the weights of edges of ${\theta }_{n}(t, 4)$ as:

It is obvious that the edges weights are different. Then

Case 3. $5tn+2\equiv 2\left(mod \; 3\right)$

$\mathrm{D}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e} \; \gamma$ as:

We can see that $ħ$ is the greatest label. For edges weights of ${\theta }_{n}(t, 4)$, we have:

It is obvious that the edges weights are distinct. So $\gamma$ is the desired edge irregular total $ħ-$ labeling, $ħ = \; \left\lceil {\frac{5tn+2}{3}} \right\rceil$. Hence

The previous results lead us to introduce the following conjecture for a general case of a uniform theta snake graph ${\theta }_{n}(t, m)$.

The previous results lead us to introduce the following conjecture for a general case of a uniform theta snake graph ${\theta }_{n}(t, m)$.

Conjecture. For uniform theta snake graph ${\theta }_{n}(t, m)$, $n\ge 2, t\ge 3, and m\ge 3$ we have

3.   Conclusions

In the current paper, we have defined a new type of a family of graph called uniform theta snake graph, ${\theta }_{n}(t, m)$. Also, the exact i value of TEISs for ${\mathtt{θ }}_{\mathrm{n}}\left(\mathrm{3, 3}\right)$, ${\mathtt{θ }}_{\mathrm{n}}(3, \mathrm{m})$ and ${\mathtt{θ }}_{\mathrm{n}}(\mathrm{t}, 3)$ has been determined. Finally, we have generalized for t, m and found TEIS of a uniform theta snake graph ${\mathtt{θ }}_{\mathrm{n}}(\mathrm{t}, \mathrm{m})$ for $\mathrm{m}\ge 3$, $\mathrm{t}\ge 3$.

Conflict of interest

All authors declare no conflict of interest in this paper.

Acknowledgment

We are so grateful to the reviewer for his many valuable suggestions and comments that significantly improved the paper.