Opuscula Math. 42, no. 3 (2022), 439-458
https://doi.org/10.7494/OpMath.2022.42.3.439
Opuscula Mathematica
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.
- A. Ahmad, O.B.S. Al-Mushayt, M. Bača, On edge irregularity strength of graphs, Appl. Math. Comput. 243 (2014), 607-610.
- M. Aigner, E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990), 439-449.
- D. Amar, O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998), 15-38.
- S. Arumugam, N. Kamatchi, On \((a,d)\)-distance antimagic graphs, Australas. J. Combin. 54 (2012), 279- 288.
- 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.
- M. Bača, S. Jendrol', M. Miller, J. Ryan, On irregular total labellings, Discrete Math. 307 (2007), 1378-1388.
- 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.
- N.H. Bong, Y. Lin, Slamin, On distance-irregular labelings of cycles and wheels, Australas. J. Combin. 69 (2017), 315-322.
- 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.
- G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congr. Numer. 64 (1988), 197-210.
- 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.
- M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B. 91 (2004), no. 1, 151-157.
- P. Majerski, J. Przybyło, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28 (2014), 197-205.
- M. Miller, C. Rodger, R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2003), 305-315.
- S. Novindasari, Marjono, S. Abusini, On distance irregular labeling of ladder graph and triangular ladder graph, Pure Math. Sci. 5 (2016), 75-81.
- 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.
- Slamin, On distance irregular labelling of graphs, Far East J. Math. Sci. 102 (2017), 919-932.
- F. Susanto, K. Wijaya, P.M. Purnama, Slamin, On distance irregular labeling of disconnected graphs, Kragujevac J. Math. 46 (2022), 507-523.
- 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
- Communicated by Mirko Horňák.
- Received: 2020-11-09.
- Revised: 2022-01-25.
- Accepted: 2022-01-26.
- Published online: 2022-04-29.
