New Results on the (Super)‎ Edge-Magic Deficiency of Chain Graphs

Abstract EN

Let G be a graph of order v and size e.

An edge-magic labeling of G is a bijection f:V(G)∪E(G)→{1,2,3,…,v+e} such that f(x)+f(xy)+f(y) is a constant for every edge xy∈E(G).

An edge-magic labeling f of G with f(V(G))={1,2,3,…,v} is called a super edge-magic labeling.

Furthermore, the edge-magic deficiency of a graph G, μ(G), is defined as the smallest nonnegative integer n such that G∪nK1 has an edge-magic labeling.

Similarly, the super edge-magic deficiency of a graph G, μs(G), is either the smallest nonnegative integer n such that G∪nK1 has a super edge-magic labeling or +∞ if there exists no such integer n.

In this paper, we investigate the (super) edge-magic deficiency of chain graphs.

Referring to these, we propose some open problems.