On the (Super) Edge-Magic Deficiency of Chain Graphs

Abstract

A graph $G$ of order $|V(G)|$ and size $|E(G)|$ is called edge-magic if there exists a bijection $f:V(G)\cup E(G)\to \{1,2,3,\dots ,|V(G)|+|E(G)|\}$ such that $f(x)+f(xy)+f(y)$ is a constant for every edge $xy\in E(G)$. An edge-magic graph $G$ is said to be super if $f(V(G))=\{1,2,3,\dots ,|V(G)|\}$. Furthermore, the edge-magic deficiency of a graph $G$, denoted $\mu (G)$, is defined as the minimum nonnegative integer $n$ such that $G\cup n{K}_1$ is edge-magic. Similarly, the \emph{super edge-magic deficiency} of a graph $G$, denoted ${\mu }_s(G)$, is either the minimum nonnegative integer $n$ such that $G\cup n{K}_1$ is super edge-magic or $+\mathrm{\infty }$ if there exists no such integer $n$. In this paper, we investigate the (super) edge-magic deficiency of chain graphs. Based on these, we propose some open problems.