Further Results On Super Edge-Magic Deficiency Of Graphs

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,\dots ,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,\dots ,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$.