  A graph $G$ is called edge-magic if there exists a bijective function
$f:V\left(G\right) \cup E\left(G\right)\rightarrow \left\{1, 2, \ldots ,
\left\vert V\left( G\right) \right\vert +\left\vert E\left( G\right)
\right\vert \right\}$ such that $f\left(u\right) + f\left(v\right) +
f\left(uv\right)$ is a constant for each $uv\in E\left( G\right) $. Also, $G$
is said to be super edge-magic if $f\left(V \left(G\right)\right) =\left\{1, 2,
\ldots , \left\vert V\left( G\right) \right\vert \right\}$. Furthermore, the
super edge-magic deficiency $ \mu_{s}\left(G\right)$ of a graph $G$ is defined
to be either the smallest nonnegative integer $n$ with the property that $G
\cup nK_{1}$ is super edge-magic or $+ \infty$ if there exists no such integer
$n$. In this paper, we introduce the parameter $l\left(n\right)$ as the minimum
size of a graph $G$ of order $n$ for which all graphs of order $n$ and size at
least $l\left(n\right)$ have $\mu_{s} \left( G \right)=+\infty $, and provide
lower and upper bounds for $l\left(G\right)$. Imran, Baig, and
Fe\u{n}ov\u{c}\'{i}kov\'{a} established that for integers $n$ with $n\equiv
0\pmod{4}$, $ \mu_{s}\left(D_{n}\right) \leq 3n/2-1$, where $D_{n}$ is the
cartesian product of the cycle $C_{n}$ of order $n$ and the complete graph
$K_{2}$ of order $2$. We improve this bound by showing that $
\mu_{s}\left(D_{n}\right) \leq n+1$ when $n \geq 4$ is even. Enomoto,
Llad\'{o}, Nakamigawa, and Ringel posed the conjecture that every nontrivial
tree is super edge-magic. We propose a new approach to attak this conjecture.
This approach may also help to resolve another labeling conjecture on trees by
Graham and Sloane.
