Opuscula Mathematica
Opuscula Math. 42, no. 3 (2022), 439-458

Distance irregularity strength of graphs with pendant vertices

Faisal Susanto
Kristiana Wijaya
Slamin
Andrea Semaničová-Feňovčíková
Abstract. A vertex \(k\)-labeling \(\phi:V(G)\rightarrow\{1,2,\dots,k\}\) on a simple graph \(G\) is said to be a distance irregular vertex \(k\)-labeling of \(G\) if the weights of all vertices of \(G\) are pairwise distinct, where the weight of a vertex is the sum of labels of all vertices adjacent to that vertex in \(G\). The least integer \(k\) for which \(G\) has a distance irregular vertex \(k\)-labeling is called the distance irregularity strength of \(G\) and denoted by \(\mathrm{dis}(G)\). In this paper, we introduce a new lower bound of distance irregularity strength of graphs and provide its sharpness for some graphs with pendant vertices. Moreover, some properties on distance irregularity strength for trees are also discussed in this paper.
Keywords: vertex \(k\)-labeling, distance irregular vertex \(k\)-labeling, distance irregularity strength, pendant vertices.
Mathematics Subject Classification: 05C78, 05C12.
Full text (pdf)
References ▼
  1. [1] A. Ahmad, O.B.S. Al-Mushayt, M. Bača, On edge irregularity strength of graphs, Appl. Math. Comput. 243 (2014), 607-610.
  2. [2] M. Aigner, E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990), 439-449.
  3. [3] D. Amar, O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998), 15-38.
  4. [4] S. Arumugam, N. Kamatchi, On \((a,d)\)-distance antimagic graphs, Australas. J. Combin. 54 (2012), 279- 288.
  5. [5] F. Ashraf, M. Bača, M. Lascśaková, A. Semaničová-Feňovčíková, On \(H\)-irregularity strength of graphs, Discuss. Math. Graph Theory 37 (2017), 1067-1078.
  6. [6] M. Bača, S. Jendrol', M. Miller, J. Ryan, On irregular total labellings, Discrete Math. 307 (2007), 1378-1388.
  7. [7] M. Bača, A. Semaničová-Feňovčíková, Slamin, K.A. Sugeng, On inclusive distance vertex irregular labelings, Electron. J. Graph Theory Appl. (EJGTA) 6 (2018), 61-83.
  8. [8] N.H. Bong, Y. Lin, Slamin, On distance-irregular labelings of cycles and wheels, Australas. J. Combin. 69 (2017), 315-322.
  9. [9] N.H. Bong, Y. Lin, Slamin, On inclusive and non-inclusive vertex irregular \(d\))-distance vertex labeling, J. Combin. Math. Combin. Comput. 113 (2020), 233-247.
  10. [10] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congr. Numer. 64 (1988), 197-210.
  11. [11] M. Kalkowski, M. Karoński, F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25 (2011), 1319-1321.
  12. [12] M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B. 91 (2004), no. 1, 151-157.
  13. [13] P. Majerski, J. Przybyło, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28 (2014), 197-205.
  14. [14] M. Miller, C. Rodger, R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2003), 305-315.
  15. [15] S. Novindasari, Marjono, S. Abusini, On distance irregular labeling of ladder graph and triangular ladder graph, Pure Math. Sci. 5 (2016), 75-81.
  16. [16] J. Przybyło, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math. 23 (2009), 511-516.
  17. [17] Slamin, On distance irregular labelling of graphs, Far East J. Math. Sci. 102 (2017), 919-932.
  18. [18] F. Susanto, K. Wijaya, P.M. Purnama, Slamin, On distance irregular labeling of disconnected graphs, Kragujevac J. Math. 46 (2022), 507-523.
About the authors ▼
Faisal Susanto
https://orcid.org/0000-0002-8012-1261
Universitas Jember, Department of Mathematics, Jalan Kalimantan 37, Jember 68121, Indonesia
Kristiana Wijaya
https://orcid.org/0000-0003-2243-147X
Universitas Jember, Department of Mathematics, Jalan Kalimantan 37, Jember 68121, Indonesia
Slamin
https://orcid.org/0000-0002-1280-8037
Universitas Jember, Department of Informatics, Jalan Kalimantan 37, Jember 68121, Indonesia
Andrea Semaničová-Feňovčíková
https://orcid.org/0000-0002-8432-9836
Technical University, Department of Applied Mathematics and Informatics, Letná 9, Košice, Slovak Republic
About the article ▼
Communicated by Mirko Horňák.
Received: 2020-11-09.
Revised: 2022-01-25.
Accepted: 2022-01-26.
Published online: 2022-04-29.
Cite this article as ▼
Faisal Susanto, Kristiana Wijaya, Slamin, Andrea Semaničová-Feňovčíková, Distance irregularity strength of graphs with pendant vertices, Opuscula Math. 42, no. 3 (2022), 439-458, https://doi.org/10.7494/OpMath.2022.42.3.439.
Download this article's citation as: