On the Super Edge-Magic Deficiency of $2$-Regular Graphs with Two Components

Abstract

A graph $G$ is called super edge-magic if there exists a bijective function $f:V(G)\cup E(G)\to \{1,2,\dots ,|V(G)|+|E(G)|\}$ such that $f(V(G))=\{1,2,\dots ,|V(G)|\}$ and $f(u)+f(v)+f(uv)$ is a constant for each $uv\in E(G)$. The super edge-magic deficiency, ${\mu }_s(G)$, of a graph $G$ is defined as 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 2-regular graphs with two components is computed, which leads us to a conjecture on the super edge-magic deficiency of graphs in this class.