Computing the Edge Irregularity Strength of Bipartite Graphs and Wheel Related Graphs

• Autorzy: Ahmad Ali , Asim Muhammad Ahsan , Assiri Basem , Semaničová-Feňovčíková Andrea

Identyfikatory

DOI

10.3233/FI-2020-1927

• Języki publikacji: EN

Abstrakty

EN

A vertex labeling φ : V(G) → {1, 2,... , k} is called an edge irregular k-labeling of a graph G if all edges in G have unique weights. The weight of an edge is defined as the sum of the labels of its incident vertices. The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G, denoted by es(G). In this paper we perform a computer based experiment dealing with the edge irregularity strength of complete bipartite graphs. We also present some bounds on this parameter for wheel related graphs.

Słowa kluczowe

EN

bipartite graph; edge irregularity strength; fan graph; friendship graph; naive algorithm; wheel graph

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 174, nr 1
• Strony: 1--13
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Ahmad Ali

• College of Computer Science & Information Technology, Jazan University, Jazan, Saudi Arabia

autor

Asim Muhammad Ahsan

• College of Computer Science & Information Technology, Jazan University, Jazan, Saudi Arabia

autor

Assiri Basem

• College of Computer Science & Information Technology, Jazan University, Jazan, Saudi Arabia

autor

Semaničová-Feňovčíková Andrea

• Department of Applied Mathematics and Informatics, Technical University, Košice, Slovak Republic

Bibliografia

• [1] Chartrand G, Jacobson MS, Lehel J, Oellermann OR, Ruiz S, Saba F. Irregular networks. Congr. Numer., 1988. 64:187-192.
• [2] Aigner M, Triesch E. Irregular assignments of trees and forests. SIAM J. Discrete Math., 1990. 3:439-449. doi:10.1137/0403038.
• [3] Amar D, Togni O. Irregularity strength of trees. Discrete Math., 1998. 190:15-38. URL https://doi.org/10.1016/S0012-365X(98)00112-5.
• [4] Bohman T, Kravitz D. On the irregularity strength of trees. J. Graph Theory, 2004. 45:241-254. URL https://doi.org/10.1002/jgt.10158.
• [5] Frieze A, Gould RJ, Karonski M, Pfender F. On graph irregularity strength. J. Graph Theory, 2002. 41:120-137.
• [6] Bača M, Jendrol’ S, Miller M, Ryan J. On irregular total labellings. Discrete Math., 2007. 307:1378-1388. URL https://doi.org/10.1016/j.disc.2005.11.075.
• [7] Ahmad A, Bača M, Bashir Y, Siddiqui MK. Total edge irregularity strength of strong product of two paths. Ars Combin., 2012. 106:449-459.
• [8] Ahmad A, Bača M, Siddiqui MK. On edge irregular total labeling of categorical product of two cycles. Theory of Comp. Systems, 2014. 54:1-12. doi:10.1007/s00224-013-9470-3.
• [9] Ahmad A, Baskoro ET, Imran M. Total vertex irregularity strength of disjoint union of helm graphs. Discuss. Math. Graph Theory, 2012. 32(3):427-434. doi:10.7151/dmgt.1619.
• [10] Jendrol’ S, J Miškuf J, Soták R. Total edge irregularity strength of complete graphs and complete bipartite graphs. Discrete Math., 2010. 310:400-407. URL https://doi.org/10.1016/j.disc.2009.03.006.
• [11] Nurdin, Baskoro ET, Salman ANM, Gaos NN. On the total vertex irregularity strength of trees. Discrete Math., 2010. 310:3043-3048. URL https://doi.org/10.1016/j.disc.2010.06.041.
• [12] Ahmad A, Al-Mushayt O, Bača M. On edge irregularity strength of graphs. Appl. Math. Comput., 2014. 243:607-610. URL https://doi.org/10.1016/j.amc.2014.06.028.
• [13] Ahmad A, Bača M, Asim MA, Hasni R. Computing edge irregularity strength of complete m-ary trees using algorithmic approach. UPB Scientific Bulletin, Series A: Applied Mathematics and Physics, 2018. 80(3):145-152.
• [14] Asim MA, Ahmad A, Hasni R. Edge irregular k-labeling for several classes of trees. Utilitas Math., 2019. 111:75-83.
• [15] Asim MA, Ali A, Hasni R. Iterative algorithm for computing irregularity strength of complete graph. Ars Combin., 2018. 138:17-24.
• [16] Tarawneh I, Hasni R, Asim MA. On the edge irregularity strength of disjoint union of star graph and subdivision of star graph. Ars Combin., 2018. 141:93-100.
• [17] Tarawneh I, Hasni R, Siddiqui MK, Asim MA. On the edge irregularity strength of disjoint union of graphs. Ars Combin., 2019. 142:239-249.
• [18] Borwein J, Borwein P, Girgensohn R, Parnes S. Experimental Mathematics: A Discussion. Archived 2008-01-21 at the Wayback Machine.
• [19] Borwein J, Bailey D. Mathematics by Experiment: Plausible Reasoning in the 21st Century, A.K. Peters. pp. vii. 2004, ISBN:978-1-56881-211-3.
• [20] Wohlin C, Runeson P, Host M, Ohlsson MC, Regnell B, Wesslen A. Experimentation in Software Engineering: An Introduction. Kluwer Academic Publishers, 2000. ISBN:0-7923-8666-3.
• [21] Figueroa-Centeno RM, Ichishima R, Muntaner-Batle FA. The place of super edge-magic labelings among other classes of labelings. Discrete Math., 2001. 231:153-168. URL https://doi.org/10.1016/S0012-365X(00)00314-9.
• [22] Ngurah AAG, Baskoro ET, Simanjuntak R. On the super edge-magic deficiencies of graphs. Australas. J. Combin., 2008. 40:3-14.
• [23] Slamin, Bača M, Lin Y, Miller M, R. Simanjuntak R. Edge-magic total labellings of wheels, fans and friendship graphs. Bulletin of the ICA, 2002. 35:89-98. URL http://repository.unej.ac.id/handle/123456789/789.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).