Some New Results 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) \rightarrow \{1,2,\ldots,p+q\} \) such that \( f(u) + f(v) + f(uv) \) is a constant for each edge \( uv \in E(G) \). Also, \( G \) is said to be super edge-magic if \( f(V(G)) = \{1,2,\ldots, p\} \). Furthermore, the super edge-magic deficiency, \( \mu_s(G) \), of a graph \( G \) is defined to be either the smallest nonnegative integer \( n \) with the property that the graph \( G \cup nK_1 \) is super edge-magic or \( +\infty \) if there exists no such integer \( n \).

In this paper, the super edge-magic deficiency of certain forests and 2-regular graphs is computed, which in turn leads to some conjectures on the super edge-magic deficiencies of graphs in these classes. Additionally, some edge-magic deficiency analogues to the super edge-magic deficiency results on forests are presented.