Totally irregular total labeling of some caterpillar graphs

Diari Indriati^a , Widodo^b , Indah E. Wijayanti^b , Kiki A. Sugeng^c , Isnaini Rosyida^d

diari indri@yahoo.co.id, widodo mathugm@yahoo.com, ind wijayanti@yahoo.com, kiki@sci.ui.ac.id, iisisnaini@gmail.com

Assume that G(V, E) is a graph with V and E as its vertex and edge sets, respectively. We have G is simple, connected, and undirected. Given a function λ from a union of V and E into a set of k-integers from 1 until k. We call the function λ as a totally irregular total k-labeling if the set of weights of vertices and edges consists of different numbers. For any u ∈ V , we have a weight wt(u) = λ(u) + P uy∈E λ(uy). Also, it is defined a weight wt(e) = λ(u) + λ(uv) + λ(v) for each e = uv ∈ E. A minimum k used in k-total labeling λ is named as a total irregularity strength of G, symbolized by ts(G). We discuss results on ts of some caterpillar graphs in this paper. The results are ts(Sp,2,2,q) = p+q−1 2 for p, q greater than or equal to 3, while ts(Sp,2,2,2,p) = 2p−1 2 , p ≥ 4.

Keywords: totally irregular total k-labeling, total irregularity strength, weight, caterpillar graph. Mathematics Subject Classification : 05C78

DOI: 10.5614/ejgta.2020.8.2.5

Received: 16 August 2019, Revised: 19 April 2020, Accepted: 7 July 2020.

^aFaculty of Mathematics and Natural Sciences, Universitas Sebelas Maret, Surakarta, Indonesia

^bDepartment of Mathematics, Universitas Gadjah Mada, Yogyakarta, Indonesia

^cDepartment of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Indonesia, Depok, Indonesia

^dDepartment of Mathematics, Universitas Negeri Semarang, Semarang, Indonesia

1. Introduction

Graph theory is one of branch of mathematics. In this field, many real life problems can be solved, especially on optimization problem [8]. Given a graph G(V, E) which is assumed as connected, simple, and undirected graph. A function that assigns a set of elements (vertex/edge) of G into a set of integers is mentioned as labeling (Wallis [12]). The labeling is said to be a total labeling if the domain is a union of vertex and edge sets.

A function f : V ∪ E → {1, 2, . . . , k} is named a vertex irregular total k-labeling if wt^f (u) 6= wt^f (v) for each u 6= v ∈ V (G), where wt(u) = f(u) + P uz∈E f(uz) [1]. A minimum k in which there exists a vertex irregular total k-labeling of G is named as a total vertex irregularity strength (tvs) of G. Indriati et al. [4] obtained tvs of generalized helm. Recently, the tvs of comb product of two cycles and two stars has been found in [10]. Meanwhile, Nurdin et al. [11] proved tvs of tree T which does not have vertex of degree two and has n pendant nodes, i.e.

\[tvs(T) = \left\lceil \frac{n+1}{2} \right\rceil. \tag{1}\]

Further, a total k-labeling g that assigns a union of V and E into {1, 2, . . . , k} is called an edge irregular when the requirement wt(xy) 6= wt(x 0 y 0 ) is satisfied for each pair xy 6= x 0 y 0 in E(G) with wt(xy) = g(x) + g(xy) + g(y). Baˇca et al. [1] mentioned the minimum k required in labeling g as a total edge irregularity strength (tes) of G. The exact value of tes of generalized web graphs was given in [2]. Recent research has found tes of some n-uniform cactus chain graphs and related chain graphs [6]. In addition, tes of any tree has been given in [7], i.e. tes(T) is equal to

\[\max\left\{ \left\lceil \frac{(|E(T)|+2)}{3} \right\rceil, \left\lceil \frac{(\Delta(T)+1)}{2} \right\rceil \right\}. \tag{2}\]

Furthermore, the total k-labeling g becomes a totally irregular total k-labeling if the set of all weights of vertices and edges contains distinct numbers [9]. A minimum k needed in the labeling g is named as total irregularity strength (ts) of G. Marzuki, et al. observed

\[ts(G) \ge \max \text{ of } \{tes(G), tvs(G)\}.\] (3)

Different with tes and tvs, the value of ts of tree has not been obtained. In order to find ts of tree, we have started the investigation for double stars Sp,q and related graphs Sp,2,q ([3], [5]). In this research, we verify ts of caterpillar graphs Sp,2,2,q and Sp,2,2,2,p.

We use the notion of caterpillar Sp,2,2,q. It is a graph which is formed from double-star Sp,q by putting two vertices on the path which are connected to the two centers of stars in Sp,q. The value of tes of graph Sp,2,2,q can be found by (2), that is

\[tes(S_{p,2,2,q}) = \max\left\{ \left\lceil \frac{\max\{p,q\}+1}{2} \right\rceil, \left\lceil \frac{p+q+3}{3} \right\rceil \right\} = \left\lceil \frac{p+q+3}{3} \right\rceil. \tag{4}\]

This graph has two vertices of degree two. Therefore, (1) cannot be used for determining tvs of this graph. The next theorem gives this parameter.

Theorem 1.1. Let Sp,2,2,q be a caterpillar with p, q greater than or equal to 3. The graph Sp,2,2,q has

\[tvs(S_{p,2,2,q}) = \left\lceil \frac{p+q-1}{2} \right\rceil.\]

Proof. Without loss of generality, we can assume that p ≤ q. We know that Sp,2,2,q contains p + q − 2 pendants, two vertices with degree two, one vertex with degree p, and one vertex of degree q. The smallest weight of each vertex is at least two. Each pendant vertex has the smallest weight which is not less than p + q − 1, i.e. the weight is a sum of two labels. Then, the largest number to label pendant vertices is not less than p+q−1 2 . The graph Sp,2,2,q consists of V (Sp,2,2,q) = {v 1 r : 1 ≤ r ≤ q − 1} ∪ {v 4 r : 1 ≤ r ≤ p − 1} ∪ {v s : s = 1, 2, 3, 4} and E(Sp,2,2,q) = {v 1 v 1 r : 1 ≤ r ≤ q − 1} ∪ {v 4 v 4 r : 1 ≤ r ≤ p − 1} ∪ {v s v ^s+1 : s = 1, 2, 3}. Next we will distinguish the following three cases, i.e. p = q = 3, p = q ≥ 4 and 3 ≤ p < q. Assume k = p+q−1 2 for all cases, and define a total k-labeling λ on each element x ∈ V (Sp,2,2,q) ∪ E(Sp,2,2,q) as follows.

We observe that each vertex and each edge has been labeled with a number which is at most \(k = \left\lceil \frac{p+q-1}{2} \right\rceil\). Further, each vertex \(x \in V(S_{p,2,2,q})\) has a weight as follows.

It is shown above, each vertex has a distinct weight under total labeling f. Therefore, \(tvs(S_{p,2,2,q}) = k = \lceil \frac{p+q-1}{2} \rceil\).

Furthermore, an exact value of ts of \(S_{p,2,2,q}\) is proved in the next theorem.

Theorem 1.2. Given a caterpillar \(S_{p,2,2,q}\) with p,q greater than or equal to 3. We get

\[ts(S_{p,2,2,q}) = \left\lceil \frac{p+q-1}{2} \right\rceil.\]

Proof. According to (3), by using Equality (4) and Theorem 1.1, the lower bound is as follows:

\[ts(S_{p,2,2,q}) \ge \max\left\{ \left\lceil \frac{p+q+3}{3} \right\rceil, \left\lceil \frac{p+q-1}{2} \right\rceil \right\} = \left\lceil \frac{p+q-1}{2} \right\rceil.\] (5)

Furthermore, we use total k-labeling λ constructed in Theorem 1.1 to get a totally irregular total k-labeling. Under labeling λ, we obtain the edge-weights below.

Case 1: For p = q = 3.

\[wt(v^{s}v_{r}^{s}) = \begin{cases} r+2, & 1 \leq r \leq p-1, \ s=1, \\ 2k+r, & 1 \leq r \leq p-1, \ s=4. \end{cases}\]\[wt(v^{s}v^{s+1}) = \begin{cases} k+2, & s=1, \\ 2k, & s=2, \\ 3k, & s=3. \end{cases}\]

Case 2: For p = q ≥ 4 and 3 ≤ p < q.

\[wt(v^{s}v_{r}^{s}) = \begin{cases} r+2, & 1 \leq r \leq q-1, \ s=1, \\ q+4+r, & 1 \leq r \leq p-1, \ s=4. \end{cases}\]\[wt(v^{s}v^{s+1}) = \begin{cases} q+2, & s=1, \\ q+3, & s=2, \\ q+4, & s=3. \end{cases}\]

It can be seen that each edge has a different weight. This concludes that λ is totally irregular total k-labeling. Thus, ts(Sp,2,2,q) = k = p+q−1 2 .

2. A graph Sp,2,2,2,p

A graph that is formed from the double-star Sp,p by inserting three vertices on the path connecting two centers of the two stars in Sp,p is called as a caterpillar Sp,2,2,2,p. Hence, Sp,2,2,2,p is a kind of tree with |E(Sp,2,2,2,p)| = 2p+2 and it has maximal degree ∆ = p. Based on (2), tes of Sp,2,2,2,p is

\[tes(S_{p,2,2,2,p}) = \max\left\{ \left\lceil \frac{p+1}{2} \right\rceil, \left\lceil \frac{2p+4}{3} \right\rceil \right\} = \left\lceil \frac{2p+4}{3} \right\rceil.\] (6)

Meanwhile, tvs of Sp,2,2,2,p is given in Theorem 2.1.

Theorem 2.1. If Sp,2,2,2,p, p ≥ 4 is a caterpillar with p ≥ 4, then

\[tvs(S_{p,2,2,2,p}) = p.\]

Proof. The graph Sp,2,2,2,p is a tree that consists of 2p − 2 pendant vertices, three vertices of degree two, and it has two vertices with degree p ≥ 4. By the similar reason as in Theorem 1.1 we get tvs(Sp,2,2,2,p) ≥ p. Let V (Sp,2,2,2,p) = {v s r : 1 ≤ r ≤ p − 1, s = 1, 5} ∪ {v s : s = 1, 2, 3, 4, 5} and E(Sp,2,2,2,p) = {v s v s r : 1 ≤ r ≤ p − 1, s = 1, 5} ∪ {v s v ^s+1 : s = 1, 2, 3, 4}. To find tvs of Sp,2,2,2,p, we create a total labeling f of an element x, x ∈ V (Sp,2,2,2,p)∪E(Sp,2,2,2,p) as follows.

Under labeling f, we can see that each vertex has label at most 2p−1 2 .

Moreover, the weight for each x ∈ V (Sp,2,2,2,p) is shown above. We can see that the each vertex has a distinct weight. Therefore, tvs(Sp,2,2,2,p) = k = 2p−1 2 .

The exact value of ts of Sp,2,2,2,p is discussed in the next theorem.

Theorem 2.2. If Sp,2,2,2,p is a caterpillar with p ≥ 4, then

\[ts(S_{p,2,2,2,p}) = p.\]

Proof. Based on (3), by using Theorem 2.1 and Equality (6) we get the lower bound of ts of Sp,2,2,2,p as follows:

\[ts(S_{p,2,2,2,p}) \ge \max \left\{ \left\lceil \frac{2p+4}{3} \right\rceil, \ p \right\} = p.\]

To construct totally irregular total k-labeling, we use the vertex irregular total k-labeling f defined in Theorem 2.1. Under labeling f, we get the edge-weights as follows.

It is obvious that each edge has a different weight. Hence, the labeling f is desired a totally irregular total k-labeling with ts(Sp,2,2,2,p) = k = p, (p ≥ 4).

Conjecture 1. For p, q ≥ 4: ts of Sp,2,2,2,q is p+q−1 2 .

References

• [1] M. Baˇca, S. Jendrol', M. Miller and J. Ryan, On irregular total labeling, Discrete Math. 307 (2007), 1378–1388.
• [2] D. Indriati, Widodo, I.E. Wijayanti, K.A. Sugeng and M. Baˇca, On total edge irregularity strength of generalized web graphs and related graphs, Mathematics in Computer Science 9 (2) (2015), 161–167.
• [3] D. Indriati, Widodo, I.E. Wijayanti and K.A. Sugeng, On total irregularity strength of double-star and related graphs, Procedia-Computer Science 74 (2015), 118–123.
• [4] D. Indriati, Widodo, I.E. Wijayanti, K.A. Sugeng, M. Baˇca and A. Semaniˇc´øv´a-Feˇnovˇc´ıkov´a, The total vertex irregularity strength of generalized helm graphs and prisms with outer pendant edges, The Australasian Journal of Combinatorics 65 (1) (2016), 14–26.
• [5] D. Indriati, Widodo, K.A. Sugeng, and I. Rosyida, The Construction of Labeling and Total Irregularity Strength of Specified Caterpillar Graph, Journal of Physics: Conference Series 855, 012018, 1–7.
• [6] I. Rosyida and D. Indriati, Computing total edge irregularity strength of some n-uniform cactus chain graphs and related chain graphs, Indonesian Journal of Combinatorics 4 (1) (2020), 53–75.
• [7] J. Ivanˇco and S. Jendroˇl', Total edge irregularity strength of trees, Discussiones Math. Graph Theory 26 (2006), 449–456.
• [8] L. Lusiantoro and W.S. Ciptono, An alternative to optimize the Indonesian's airport design: an application of minimum spanning tree (MST. Technique), Gadjah Mada International Journal of Business 14 (3) (2012).
• [9] C.C. Marzuki, A.N.M. Salman and M. Miller, On the total irregularity strength of cycles and paths, Far East Journal of Mathematical Sciences 1 (2013), 1–21.
• [10] R. Ramdani, On the total vertex irregularity strength of comb product of two cycles and two stars, Indonesian Journal of Combinatorics 3 (2) (2019), 79–94.
• [11] Nurdin, E.T. Baskoro, A.N.M. Salman and N.N. Gaos, On the total vertex irregularity strength of trees, Discrete Math. 310 (2010), 3043–3048.
• [12] W.D. Wallis, Magic graphs, Birkhauser Boston (2001).