A unified approach to total vertex irregularity strength

Articles in Press

Document Type : Research Paper

Author

Algebra Research Group, Institut Teknologi Bandung, Jl. Ganesa No. 10, Bandung 40132, Indonesia

Abstract

We develop a unified framework for computing the total vertex irregularity strength (tvs) of diverse graph classes, significantly extending our prior work in Barra et al. This comprehensive approach generalizes and enhances earlier methods, offering a robust technique applicable to a wide range of graph structures. A notable achievement is resolving an open problem by determining the tvs for simple 2-regular graphs, confirming the conjecture by Ahmad et al. Furthermore, our framework provides unified proofs for the tvs of cycles, paths, prisms, wheels, helm graphs, and friendship graphs. Importantly, the versatility of this method suggests its potential utility in computing tvs for additional graph classes, broadening its impact in graph theory and computational applications.

Keywords

Main Subjects

References

[1] A. Ahmad, K. M. Awan, I. Javaid and S. Slamin, Total vertex irregularity strength of wheel related graphs, Australas. J. Combin., 51 (2011) 147–156.
[2] A. Ahmad, M. Baˇca and M. K. Siddiqui, Irregular total labeling of disjoint union of prisms and cycles, Australas. J. Combin., 59 (2014) 98–106.
[3] M. Anholcer, M. Kalkowski and J. Przybylo, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math., 309 no. 21 (2009) 6316–6317.
[4] M. Baˇca, S. Jendrol’, M. Miller and J. Ryan, On irregular total labellings, Discrete Math., 307 no. 11–12 (2007) 1378–1388.
[5] A. Barra and M. Afifurrahman, The total vertex irregularity strength for cubic graphs with a perfect matching, Discrete Math., 348 no. 5 (2025) 10 pp.
[6] G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz and F. Saba, Irregular networks. 250th Anniversary Conference on Graph Theory (Fort Wayne, IN, 1986), Congr. Numer., 64 (1988) 197–210.
[7] R. J. Faudree and J. Lehel, Bound on the irregularity strength of regular graphs, In Colloq. Math. Soc. J´anos Bolyai, 52, North-Holland, Amsterdam, (1988) 247–256.
[8] M. Kalkowski, M. Karonski and F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math., 25 (2011) no. 3 1319–1321.
[9] P. Majerski and J. Przybylo, Total vertex irregularity strength of dense graphs, J. Graph Theory, 76 no. 1 (2013) 34–41.
[10] P. Majerski and Jakub Przybylo, On the irregularity strength of dense graphs, SIAM J. Discrete Math., 28 no. 1 (2014) 197–205.
[11] B. Nurdin, E. T. Baskoro, A. N. M. Salman and N. N. Gaos, On the total vertex irregularity strength of trees, Discrete Math., 310 no. 21 (2010) 3043–3048.
[12] J. Przybylo and F. Wei, On the asymptotic confirmation of the Faudree-Lehel conjecture for general graphs, Combinatorica, 43 no. 4 (2023) 791–826.
[13] J. Przybylo and F. Wei, Short proof of the asymptotic confirmation of the Faudree-Lehel conjecture, Electron. J. Combin., 30 no. 4 Paper No. 4.27 (2023) 13 pp.
[14] K. Wijaya and Slamin, Total vertex irregular labelings of wheels, fans, suns and friendship graphs, J. Combin. Math. Combin. Comput., 65 (2008) 103–112.
[15] K. Wijaya, Slamin, Surahmat, and Stanislav Jendrol’, Total vertex irregular labeling of complete bipartite graphs, J. Combin. Math. Combin. Comput., 55 (2005) 129–136.
Transactions on Combinatorics

Articles in Press, Corrected Proof
Available Online from 07 October 2026

Files

History

  • Receive Date: 06 May 2025
  • Revise Date: 02 September 2026
  • Accept Date: 07 September 2026
  • Published Online: 07 October 2026

Share

How to cite

Statistics