Totally irregular total labeling of some caterpillar graphs

Diari Indriati, W. Widodo, Indah E. Wijayanti, Kiki A. Sugeng, Isnaini Rosyida


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 uV, we have a weight wt(u)=λ(u)+ ∑{uy ∈ E} λ(uy). Also, it is defined a weight wt(e)= λ(u)+ λ(uv) + λ(v) for each e=uvE. 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(S{p,2,2,q}) = ⌈ (p+q-1)/2 ⌉ for p, q greater than or equal to 3, while ts(S{p,2,2,2,p}) = ⌈(2p-1)/2 ⌉, p ≥ 4.


totally irregular total $k$-labeling, total irregularity strength, weight, caterpillar graph

Full Text:




M. Baca, S. Jendrol’, M. Miller and J. Ryan, On irregular total labeling, Discrete Math. 307 (2007), 1378–1388.

D. Indriati, Widodo, I.E. Wijayanti, K.A. Sugeng and M. Baca, On total edge irregularity strength of generalized web graphs and related graphs, Mathematics in Computer Science 9 (2) (2015), 161–167.

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.

D. Indriati, Widodo, I.E. Wijayanti, K.A. Sugeng, M. Baca and A. Semanicøva- Fenovcıkova, 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.

D. Indriati, Widodo, K.A. Sugeng, and I. Rosyida, The Construction of Labeling and Total Irregularity Strength of Specified Caterpillar Graph, Journal of Physics: Confer- ence Series 855, 012018, 1–7.

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.

J. Ivanco and S. Jendrol’, Total edge irregularity strength of trees, Discussiones Math. Graph Theory 26 (2006), 449–456.

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).

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.

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.

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.

W.D. Wallis, Magic graphs, Birkhauser Boston (2001).


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats