On edge irregularity strength of different families of graphs

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-5873

Keywords:

irregular assignment, irregularity strength, edge irregularity strength, pendant edges, snake graphs, linear phenylene graph PHn, Bn graph

Abstract

Edge irregular mapping or vertex mapping h : V (G) → {1,2,3,...,s} is a mapping of vertices in such a way that all edges have distinct weights. We evaluate weight of any edge by using equation wth(cd) = h(c) + h(d), ∀c, d ∈ V(G) and ∀cd ∈ E(G). Edge irregularity strength denoted by es(G) is a minimum positive integer used to label vertices to form edge irregular labeling. In this paper, we find exact value of edge irregularity strength of linear phenylene graph PHn, Bn graph and different families of snake graph.

Author Biographies

Muhammad Imran, Concordia College Kasur Campus.

Department of Mathematics.

Murat Cancan, Yuzuncu Yil University

Faculty of Education.

Yasir Ali, Concordia College Kasur Campus.

Department of Mathematics.

Anum, Concordia College Kasur Campus.

Department of Mathematics.

Jamila Aslam, Concordia College Kasur Campus.

Department of Mathematics.

References

A. Ahmad, M. Baca, Y. Bashir, and M. K. Siddiqui, “Total edge irregularity strength of strong product of two paths”, Ars Combinatoria, vol. 106, pp. 449-459, 2012.

A. Ahmad, M. Baca, and M. K. Siddiqui, “On edge irregular total labeling of categorical product of two cycles”. Theory of Computing Systems, vol. 54, no. 1, pp. 1-12, 2014. https://doi.org/10.1007/s00224-013-9470-3

A. Ahmad, O. B. S. Al-Mushayt, and M. Baca, “On edge irregularity strength of graphs”, Appl. Math. Comput, vol. 243, pp. 607-610, 2014. https://doi.org/10.1016/j.amc.2014.06.028

A. Ahmad, M. Arshad, and G. Iarkov, “Irregular labelings of helm and sun graphs”. AKCE International Journal of Graphs and combinatorics, vol. 12, no. 2-3, pp. 161-168, 2015. https://doi.org/10.1016/j.akcej.2015.11.010

A. Ahmad, M. Baca, and M. F. Nadeem, “On edge irregularity strength of Toeplitz graphs”, U.P.B. Sci. Bull., Series A, vol. 78, no. 4, pp. 155-162, 2016.

A. Ahmad, M. A. Asim, B. Assiri, and A. Semaničová-Feňovčíková, “Computing the edge irregularity strength of bipartite graphs and wheel related graphs”, Fundamenta Informaticae, vol. 174, no. 1, pp. 1-13, 2020. https://doi.org/10.3233/fi-2020-1927

D. Amar, and O. Togni, “Irregularity strength of trees”, Discrete Math, vol. 190, pp. 15-38, 1998. https://doi.org/10.1016/s0012-365x(98)00112-5

M. Anholcer, M. Kalkowski, and J. Przybyo, “A new upper bound for the total vertex irregularity strength of graphs”, Discrete Math., vol. 309, no. 21, pp. 6316-6317, 2009. https://doi.org/10.1016/j.disc.2009.05.023

O. B. S. Al-Mushayt, A. Ahmad, and M. K. Siddiqui, “On the total edge irregularity strength of hexagonal grid graphs”, Australasian J. Combinatorics, vol. 53, 263-272, 2012.

O. S. Al-Mushayt, “On edge irregularity strength of products of certain families of graphs with path P-2”, Ars Combinatoria, vol. 135, pp. 323-334, 2017.

E. T. Baskoro, A. N. M. Salman, and N. N. Gaos, “On the total vertex irregularity strength of trees”, Discrete Math., vol. 310, no. 21, pp. 3043-3048, 2010. https://doi.org/10.1016/j.disc.2010.06.041

M. Baca, and S. Jendrol, M. Miller, and J. Ryan, “On irregular total labellings”, Discrete Mathematics, pp. 1378-1388, vol. 307, no. 11-12, 2007. https://doi.org/10.1016/j.disc.2005.11.075

M. Baca, and M. K. Siddiqui, “Total edge irregularity strength of generalized prism”. Appl. Math. Comput, vol. 235, pp. 168-173, 2014. https://doi.org/10.1016/j.amc.2014.03.001

T. Bohman, and D. Kravitz, “On the irregularity strength of trees”, J. Graph Theory, vol. 45, pp. 241-254, 2004. https://doi.org/10.1002/jgt.10158

G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz, and F. Saba, “Irregular networks”, Congr. Numer., vol. 64, pp. 187-192, 1988.

A. Frieze, R. J. Gould, M. Karonski, and F. Pfender, “On graph irregularity strength”, J. Graph Theory, vol. 41, pp. 120-137, 2002.https://doi.org/10.1002/jgt.10056

K. M. M. Haque, “Irregular total labellings of generalized Petersen graphs”, Theory of Computing Systems, vol. 50, no. 3, pp. 537-544, 2012. https://doi.org/10.1007/s00224-011-9350-7

J. Ivano, and S. Jendrol, “Total edge irregularity strength of trees”, Discussiones Mathematicae Graph Theory, vol. 26, no. 3, pp. 449-456, 2006. https://doi.org/10.7151/dmgt.1337

M. Imran, A. Aslam, S. Zafar, and W. Nazeer, “Further results on edge irregularity strength of graphs”. Indonesian Journal of Combinatorics, vol. 1, no. 2, pp. 82-91, 2017. https://doi.org/10.19184/ijc.2017.1.2.5

S. Jendrol, J. Mikuf, and R. Sotk, “Total edge irregularity strength of complete graphs and complete bipartite graphs”, Discrete Mathematics, vol. 310, no. 3, pp. 400-407, 2010.https://doi.org/10.1016/j.disc.2009.03.006

M. Kalkowski, M. Karonski, and F. Pfender, “A new upper bound for the irregularity strength of graphs”, SIAM J.Discrete Math., vol. 25, no. 3, pp. 1319-1321, 2011. https://doi.org/10.1137/090774112

P. Majerski, and J. Przybyo, “Total vertex irregularity strength of dense graphs”. Journal of Graph Theory, vol. 76, no. 1, pp. 34-41, 2014. https://doi.org/10.1002/jgt.21748

P. Majerski, and J. Przybylo, “On irregularity strength of dense graphs”, J. Graph Theory, vol. 28, no. 1, pp. 197-205, 2014. https://doi.org/10.1137/120886650

J. Przybyo, “Linear bound on the irregularity strength and the total vertex irregularity strength of graphs”, SIAM Journal on Discrete Mathematics, vol. 23, no. 1, pp. 511-516, 2009. https://doi.org/10.1137/070707385

M. K. Siddiqui, “On edge irregularity strength of subdivision of star Sn”, International Journal of Mathematics and Soft Computing, vol. 2, no. 1, pp. 75-82, 2012. https://doi.org/10.26708/ijmsc.2012.1.2.09

M. K. Siddiqui, A. Ahmad, M. F. Nadeem, and Y. Bashir, “Total edge irregularity strength of the disjoint union of sun graphs”, International Journal of Mathematics and Soft Computing, vol. 3, no. 1, pp. 21-27, 2013. https://doi.org/10.26708/ijmsc.2013.1.3.02

I. Tarawneh, R. Hasni, and A. Ahmad, “On the edge irregularity strength of corona product of graphs with paths”, Appl. Math. E-Notes, vol. 16, pp. 80-87, 2016. https://doi.org/10.1142/s1793830920500834

I. Tarawneh, R. Hasni, and A. Ahmad, “On the edge irregularity strength of corona product of cycle with isolated vertices”, AKCE International Journal of Graphs and Combinatorics, vol. 13, no. 3, pp. 213-217, 2016. https://doi.org/10.1016/j.akcej.2016.06.010

I. Tarawneh, R. Hasni, and M. A. Asim, “On the edge irregularity strength of disjoint union of star graph and subdivision of star graph”, Ars Combinatoria, vol. 141, pp. 93-100, 2018.

I. Tarawneh, R. Hasni, and A. Ahmad, “On the edge irregularity strength of grid graphs”, AKCE International Journal of Graphs and Combinatorics, vol. 17, no. 1, pp. 414-418, 2020. https://doi.org/10.1016/j.akcej.2018.06.011

X. Zhang, M. Cancan, M. F. Nadeem, and M. Imran, “Edge irregularity strength of certain families of comb graph”, Proyecciones (Antofagasta), vol. 39, no. 4, pp. 787-797, 2020. https://doi.org/10.22199/issn.0717-6279-2020-04-0049

Published

2023-11-27

How to Cite

[1]
Muhammad Imran, Murat Cancan, Y. Ali, Anum, and J. Aslam, “On edge irregularity strength of different families of graphs”, Proyecciones (Antofagasta, On line), vol. 42, no. 6, pp. 1549-1566, Nov. 2023.

Issue

Vol. 42 No. 6 (2023)

Section

Artículos

Copyright (c) 2023 Muhammad Imran, Murat Cancan, Yasir Ali, Anum, Jamila Aslam

Creative Commons License

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

  • No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

Most read articles by the same author(s)