Further Results On Super Edge-Magic Deficiency Of Graphs

S.M. Hegde1, Sudhakar Shetty2, P. Shankaran2
1Department of Mathematical and Computational Sciences, National Institute of Technology Karnataka, Surathkal, INDIA.
2Department of Mathematics, Nitte Education Trust, Nitte, 574110, Karnataka, INDIA.

Abstract

Acharya and Hegde have introduced the notion of strongly \(k\)-indexable graphs: A \((p,q)\)-graph \(G\) is said to be strongly \(k\)-indexable if its vertices can be assigned distinct integers \(0,1,2,\ldots,p-1\) so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices can be arranged as an arithmetic progression \(k,k+1,k+2,\ldots,k+(q-1)\). Such an assignment is called a strongly \(k\)-indexable labeling of \(G\). Figueroa-Centeno et al. have introduced the concept of super edge-magic deficiency of graphs: Super edge-magic deficiency of a graph \(G\) is the minimum number of isolated vertices added to \(G\) so that the resulting graph is super edge-magic. They conjectured that the super edge-magic deficiency of the complete bipartite graph \(K_{m,n}\) is \((m-1)(n-1)\) and proved it for the case \(m=2\). In this paper, we prove that the conjecture is true for \(m=3,4,5\), using the concept of strongly \(k\)-indexable labelings \(^1\).