Some Results on Super Edge-Magic Deficiency of Graphs

M. Imran   ; A. Q. Baig   ; A. S. Feňovčíková

Kragujevac Journal of Mathematics, Tome 44 (2020) no. 2, p. 237

Résumé

An edge-magic total labeling of a graph $G$ is a bijection $f: \linebreak V(G)\cup E(G)\to \{1, 2, …, |V(G)|+|E(G)|\}$, where there exists a constant $k$ such that $f(u)+f(uv)+f(v)=k$, for every edge $uv\in E(G)$. Moreover, if the vertices are labeled with the numbers $1, 2, …, |V(G)|$ such a labeling is called a super edge-magic total labeling. The super edge-magic deficiency of a graph $G$, denoted by $\mu_s(G)$, is the minimum nonnegative integer $n$ such that $G\cup nK_1$ has a~super edge-magic total labeling or is defined to be $\infty$ if there exists no such $n$. In this paper we study the super edge-magic deficiencies of two types of snake graph and a prism graph $D_n$ for $n\equiv 0\pmod 4$. We also give an exact value of super edge-magic deficiency for a ladder $P_n ×K_2$ with $1$ pendant edge attached at each vertex of the ladder, for $n$ odd, and an exact value of super edge-magic deficiency for a square of a path $P_n$ for $n\ge 3$.

Détail

Keywords: super edge-magic total labeling, super edge-magic deficiency, block graph, snake graph, prism, corona of graphs, square of graph