On the Sequential Number and Super Edge-Magic Deficiency of Graphs

Abstract

A graph $G$ is called 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(u)+f(v)+f(uv)$ is a constant for each $uv\in E(G)$. Also, $G$ is called super edge-magic if $f(V(G))=\{1,2,\dots ,|V(G)|\}$. Moreover, the super edge-magic deficiency, ${\mu }_s(G)$, of a graph $G$ is defined to be 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, we introduce the notion of the sequential number, $\sigma (G)$, of a graph $G$ without isolated vertices to be either the smallest positive integer $n$ for which it is possible to label the vertices of $G$ with distinct elements from the set $\{0,1,\dots ,n\}$ in such a way that each $uv\in E(G)$ is labeled $f(u)+f(v)$ and the resulting edge labels are $|E(G)|$ consecutive integers, or $+\mathrm{\infty }$ if there exists no such integer $n$. We prove that $\sigma (G)={\mu }_s(G)+|V(G)|–1$ for any graph $G$ without isolated vertices, and $\sigma (K_{m,n})=mn$ for every two positive integers $m$ and $n$, which allows us to settle the conjecture that ${\mu }_s(K_{m,n})=(m-1)(n-1)$ for every two positive integers $m$ and $n$.