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)\to \{1,2,\dots ,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,\dots ,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 n{K}_1$ is super edge-magic or $+\mathrm{\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.