Zero-Sum Magic Labelings and Null Sets of Regular Graphs

Saieed Akbari, Farhad Rahmati, Sanaz Zare

Abstract


For every $h\in  \mathbb{N}$, a graph $G$ with the vertex set $V(G)$ and the  edge set $E(G)$ is said to be $h$-magic if there exists a labeling $l : E(G) \rightarrow\mathbb{Z}_h \setminus \{0\}$  such that the induced vertex labeling $s : V (G) \rightarrow \mathbb{Z}_h$, defined  by $s(v) =\sum_{uv \in E(G)} l(uv)$ is a constant map. When this constant is zero, we say that $G$ admits a zero-sum $h$-magic labeling. The null set of a graph $G$, denoted by $N(G)$, is the set of all natural numbers $h \in \mathbb{ N} $ such that $G$ admits a zero-sum $h$-magic labeling.  In 2012, the null sets of 3-regular graphs were determined. In this paper we show that if $G$ is an $r$-regular graph, then for even $r$ ($r > 2$), $N(G)=\mathbb{N}$ and for odd $r$ ($r\neq5$),  $\mathbb{N} \setminus \{2,4\}\subseteq N(G)$. Moreover,  we prove that if $r$ is odd and $G$ is a $2$-edge connected $r$-regular graph ($r\neq 5$), then $ N(G)=\mathbb{N} \setminus \{2\}$. Also, we show that if $G$ is a $2$-edge connected bipartite graph, then $\mathbb{N} \setminus \{2,3,4,5\}\subseteq N(G)$.

Keywords


Magic labeling; Null set; Zero-sum flows; Regular graph; Bipartite graph

Full Text: PDF