Application of the Combinatorial Nullstellensatz to magic-type graph labelings

Abstract

Let $G=(V,E)$ be a simple graph, and let $k\ge 2$ be an integer. For an edge labeling $h:E(G)\to {\mathbb{Z}}_k\backslash \{0\}$, define the induced vertex label by \[ h^+(v)=\sum_{e \ni v} h(e) \pmod{k}. \] For $t\in {\mathbb{Z}}_k$, we say that $G$ is \emph{$t$-sum ${\mathbb{Z}}_k$-magic} if there exists such a labeling $h$ satisfying \[ h^+(v)=t \qquad\text{for all }v\in V. \] We say that $G$ is \emph{${\mathbb{Z}}_k$-magic} if $G$ is $t$-sum ${\mathbb{Z}}_k$-magic for some $t\in {\mathbb{Z}}_k$. Similarly, if there exists an edge labeling $h:E(G)\to {\mathbb{Z}}_k\backslash \{0\}$ such that the induced vertex labeling $h^{+}(v)={\sum }_{e\ni v}h(e)$ (mod $k$) is injective, then $G$ is called \emph{${\mathbb{Z}}_k$-antimagic}. In this paper, we use the Combinatorial Nullstellensatz to analyze these two types of magic graph labelings.

15 pages, 2 figures