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, \ldots, |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, \ldots, |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 nK_1\) is super edge-magic, or \(+\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, \ldots, 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 \(+\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\).