On The Super Edge-Magic Deficiency of Graphs

Abstract

A \((p,q)\) graph \(G\) is called edge-magic if there exists a bijective function \(f: V(G) \cup E(G) \to \{1,2,\ldots,p+q\}\) such that \(f(u) + f(v) + f(uv) = k\) is a constant for any edge \(uv \in E(G)\). Moreover, \(G\) is said to be super edge-magic if \(f(V(G)) = \{1,2,\ldots, p\}\). The question studied in this paper is for which graphs it is possible to add a finite number of isolated vertices so that the resulting graph is super edge-magic. If it is possible for a given graph \(G\), then we say that the minimum such number of isolated vertices is the super edge-magic deficiency, \(\mu_s(G)\) of \(G\); otherwise we define it to be \(+\infty\).