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

Article type: Research Article

Authors: Ahmad, Ali^a | Asim, Muhammad Ahsan^a | Assiri, Basem^a | Semaničová-Feňovčíková, Andrea^{b; *; †}

Affiliations: [a] College of Computer Science & Information Technology, Jazan University, Jazan, Saudi Arabia. [email protected], [email protected], [email protected] | [b] Department of Applied Mathematics and Informatics, Technical University, Košice, Slovak Republic. [email protected]

Correspondence: [†] Address for correspondence: Department of Applied Mathematics and Informatics, Technical University, Košice, Slovak Republic.

Note: [*] The research for this article was supported by APVV-15-0116 and by VEGA 1/0233/18.

Abstract: 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.

Keywords: edge irregularity strength, bipartite graph, wheel graph, fan graph, friendship graph, naive algorithm

DOI: 10.3233/FI-2020-1927

Journal: Fundamenta Informaticae, vol. 174, no. 1, pp. 1-13, 2020