Computing total edge irregularity strength of some n-uniform cactus chain graphs and related chain graphs

Isnaini Rosyida, Diari Indriati


Given graph G(V,E). We use the notion of total k-labeling which is edge irregular. The notion of total edge irregularity strength (tes) of graph G means the minimum integer k used in the edge irregular total k-labeling of G. A cactus graph G is a connected graph where no edge lies in more than one cycle. A cactus graph consisting of some blocks where each block is cycle Cn with same size n is named an n-uniform cactus graph. If each cycle of the cactus graph has no more than two cut-vertices and each cut-vertex is shared by exactly two cycles, then G is called n-uniform cactus chain graph. In this paper, we determine tes of n-uniform cactus chain graphs C(Cnr) of length r for some n ≡ 0 mod 3. We also investigate tes of related chain graphs, i.e. tadpole chain graphs Tr(4,n) and Tr(5,n) of length r. Our results are as follows: tes(C(Cnr)) = ⌈(nr + 2)/3⌉ ; tes(Tr(4,n)) = ⌈((5+n)r+2)/3⌉ ; tes(Tr(5,n)) = ⌈((5+n)r+2)/3⌉.


Edge irregular total k-labeling; total edge irregularity strength; uniform; cactus chain; tadpole graph

Full Text:




A. Ahmad, M. Baca, Y. Bashir, and M. K. Siddiqui, Total edge irregularity strength of strong product of two paths, Ars Combin. 106 (2012), 449–459.

A. Ahmad, A. Gupta, and R.Simanjuntak, Computing the edge irregularity strengths of chain graphs and the join of two graphs, Electron. J. Graph Theory Appl. 6(1) (2018), 201–207

S. Alikhani, S. Jahari, M. Mehryar, and R. Hasni, Counting the number of dominating sets of cactus chains, J. Optoelectron. Adv. M. 8(9-10) (2014), 955–960.

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

M. Baca, S. Jendrol, K. Kathiresan, K. Muthugurupackiam, and A. Semanicova ́-Fenovcikova, A Survey of Irregularity Strength, Electron Notes Discrete Math. 48 (2015), 19–26.

K. Borissevich and T. Doslic, Counting dominating sets in cactus chains, Filomat 29(8) (2015), 1847–1855.

J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 19 (2017) #DS6.

M. Imran, A. Aslam, S. Zafar, and W. Nazeer, Further results on edge irregularity strength of graphs, Indones. J. Combin. 1(2) (2017), 82–91.

D. Indriati, Widodo, I.E., Wijayanti, and K.A. Sugeng, On the total edge irregularity strength of generalized helm, AKCE Int. J. Graphs Comb. 10(2) (2013), 147–155.

D. Indriati, Widodo, I. E. Wijayanti, K. A. Sugeng, and M. Bac ̆a, On total edge irregularity strength of generalized web graphs and related graphs, Math. Comput. Sci. 9 (2015), 161– 167.

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

S. Jendrol, J. Miskuf, and R. Sotak, Total edge irregularity strength of complete graphs and complete bipartite graphs, Discrete Math. 310(3) (2010), 400–407.

P. Jeyanthi and A. Sudha, Total edge irregularity strength o fsome families of graphs, Utilitas Math., 109 (2018), 139–153.

J. Miskuf and S. Jendrol, On total edge irregularity strength of the grids, Tatra Mt. Math. Publ. 36 (2007), 147–151.

Nurdin, A. N. M. Salman, and E. T. Baskoro, The total edge irregularity strengths of the corona product of paths with some graphs, J. Combin. Math. Combin. Comput. 65 (2008), 163–175.

I. Rosyida and D. Indriati, On total edge irregularity strength of some cactus chain graphs with pendant vertices, J. Phys. Conf. Ser. J 1211(012016) (2019), 1–9.

A. Sadeghieh, S. Alikhani, N. Ghanbari, and A. J. M. Khalaf, Hosoya polynomial of some cactus chains, Cogent Math. 4 (1) (2017), 1–7.

M. K. Siddiqui, On edge irregularity strength of subdivision of star Sn, Int. J. of Math and Soft Comput. 2(1) (2012), 75–82.


  • There are currently no refbacks.

ISSN: 2541-2205

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

View IJC Stats