% LaTeX file for a 1 page document \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{latexsym} \usepackage{amsmath,graphicx,amsfonts} \newtheorem{prethm}{{\bf Theorem}} \renewcommand{\theprethm}{{\arabic{prethm}}} \newenvironment{thm}{\begin{prethm}{\hspace{-0.5 em}{\bf.}}}{\end{prethm}} \newtheorem{prepro}[prethm]{Proposition} \newenvironment{pro}{\begin{prepro}{\hspace{-0.5 em}{\bf.}}}{\end{prepro}} \newtheorem{prelem}[prethm]{Lemma} \newenvironment{lem}{\begin{prelem}{\hspace{-0.5 em}{\bf.}}}{\end{prelem}} \newtheorem{precor}[prethm]{Corollary} \newenvironment{cor}{\begin{precor}{\hspace{-0.5 em}{\bf.}}}{\end{precor}} %\newenvironment{prelem}{\begin{prethm}{\hspace{-0.5 % em}{\bf.}}}{\end{prethm}} \newtheorem{prerem}[prethm]{{\bf Remark}} %\renewcommand{\thepreremark}{{\arabic{preremark}}} \newenvironment{rem}{\begin{prerem}\em{\hspace{-0.5 em}{\bf.}}}{\end{prerem}} \newtheorem{preconj}[prethm]{{\bf Conjecture}} \newenvironment{conj}{\begin{preconj}{\hspace{-0.5 em}{\bf.}}}{\end{preconj}} \newtheorem{preexample}{{\bf Example}} \renewcommand{\thepreexample}{{\arabic{preexample}}} \newenvironment{example}{\begin{preexample}\em{\hspace{-0.5 em}{\bf.}}}{\end{preexample}} \newtheorem{preproof}{{\bf Proof.}} \renewcommand{\thepreproof}{} \newenvironment{proof}[1]{\begin{preproof}{\rm #1}\hfill{$\Box$}}{\end{preproof}} \newenvironment{prooff}[1]{\begin{preproof}{\rm #1}}{\end{preproof}} \newcommand{\noi}{\noindent} \newcommand{\om}{\omega} \newcommand{\rank}{{\rm rank}} \newcommand{\pr}{\preceq} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\la}{\lambda} \newcommand{\tr}{{\rm tr}} \newcommand{\ie}{{\rm IE}} \newcommand{\lel}{{\rm LEL}} \newcommand{\die}{{\rm DIE}} \newcommand{\p}{\partial} \newcommand{\x}{{\bf x}} \newcommand{\y}{{\bf y}} \newcommand{\rb}{{\bf r}} \newcommand{\s}{{\bf s}} \newcommand{\e}{\epsilon} \newcommand{\M}{{\cal M}} \newcommand{\C}{{\cal C}} \newcommand{\wt}{\widetilde} \newcommand{\f}{\footnotesize} \renewcommand{\thefootnote} \begin{document} \title{Zero-Sum Magic Labelings and Null Sets of Regular Graphs} \author{Saieed Akbari$^{\,\rm a,c}$\and Farhad Rahmati$^{\,\rm b}$\and Sanaz Zare$^{\,\rm b,c}$ \and{}\\ {\footnotesize {$^{\rm a}$Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran}}\\ {\footnotesize{$^{\rm b}$Department of Mathematical Sciences, Amirkabir University of Technology, Tehran, Iran}}\\ {\footnotesize {$^{\rm c}$School of Mathematics, Institute for Research in Fundamental Sciences (IPM),}}\\ {\footnotesize {P.O. Box 19395-5746, Tehran, Iran}}} \footnotetext{E-mail Addresses: {\tt s\_akbari@sharif.edu} (S. Akbari), {\tt frahmati@aut.ac.ir} (F. Rahmati), {\tt sa\_zare\_f@yahoo.com} (S. Zare)} \date{\dateline{ ?, 2013}{ ?, 2014}{, 2014}\\ \small Mathematics Subject Classifications: 05C78} \maketitle \begin{abstract} {\small \noindent 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 {\it $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 {\it zero-sum $h$-magic labeling}. The {\it null set} of a graph $G$, denoted by {\it $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) $. } \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} \hspace{0.5cm} Let $G$ be a finite and undirected graph with vertex set $V(G)$ and edge set $E(G)$. A graph in which multiple edges are admissible is called a {\it multigraph}. An {\it $r$-regular} graph is a graph each of whose vertex has degree $r$. The degree of a vertex $u$ in $G$ is denoted by $d_G(u)$. A {\it cut-edge} of $G$ is an edge in $E(G)$ such that its deletion results in a graph with one more connected component than $G$ has. A graph $G$ is {\it $n$-edge connected } if the minimum number of edges whose removal would disconnect $G$ is at least $n$. We denote the complete graph and the cycle of order $n$ by $K_n$ and $C_n$, respectively. A {\it wheel} is a graph with $n$ vertices, formed by connecting a single vertex to all vertices of $C_{n-1}$ and denoted by $W_n$. A {\it pendant edge} is an edge incident with a vertex of degree $1$.\\ A subgraph $F$ of $G$ is a {\it factor} of $G$ if $F$ is a spanning subgraph of $G$. If a factor $F$ is $k$-regular for some integer $k \geq 0$, then $F$ is a {\it $k$-factor}. Thus a $2$-factor is a disjoint union of cycles that cover all vertices of $G$. A {\it $k$-factorization} of $G$ is a partition of the edges of $G$ into disjoint $k$-factors. For integers $a$ and $b$ with $1 \leq a \leq b$, an {\it $[a, b]$-multigraph } is defined to be a multigraph $G$ such that for every $v\in V(G)$, $a\leq d_G(v)\leq b$. For a set $\{a_1, \ldots ,a_r\}$ of non-negative integers an {\it $\{a_1, \ldots , a_r\}$-multigraph} is a multigraph each of whose vertices has degree from the set $\{a_1, \ldots ,a_r\}$. Analogously, an {\it $[a, b]$-factor} and an {\it $\{a_1, \ldots , a_r\}$-factor} can be defined.\\ Let $G$ be a graph. A {\it zero-sum flow} for $G$ is an assignment of non-zero real numbers to the edges of $G$ such that the sum of values of all edges incident with each vertex is zero. Let $k$ be a natural number. A {\it zero-sum $k$-flow} is a zero-sum flow with values from the set \mbox{$\{\pm 1,\ldots,\pm(k-1)\}$}.\\ For an abelian group $A$, written additively, any mapping $l : E(G) \rightarrow A $ is called a {\it labeling} of a graph $G$. Given a labeling on the edge set of $G$, one can introduce a vertex labeling $s : V (G) \rightarrow A$, defined by $s(v) =\sum_{uv \in E(G)} l(uv)$, for $v \in V(G)$. A graph $G$ is said to be {\it $A$-magic} if there is a labeling $l : E(G) \rightarrow A\setminus \{0\}$ such that for each vertex $v$, the sum of the labels of edges incident with $v$ is all equal to the same constant, that is there exists constant $c$ such that for all vertices $v$, $s(v) = c \in A$. We call this labeling an {\it $A$-magic labeling} of $G$. In general, an $A$-magic graph may admit more than one $A$-magic labeling. For every positive integer $h\geq 2$, a graph $G$ is called an { \it $h$-magic graph} if there is a $\mathbb{Z}_h$-magic labeling of $G$. A graph $G$ is said to be {\it zero-sum $h$-magic} if there is an edge labeling from $E(G)$ into $\mathbb{Z}_h \setminus \{0\}$ such that the sum of values of all edges incident with each vertex is zero. If $s(v)=0$ for a fixed vertex $v\in V(G)$, then we say that {\it zero-sum $h$-magic rule} holds in $v$. The {\it null set} of a graph $G$, denoted by {\it $N(G)$}, is the set of all natural numbers $h \in \mathbb{ N} $ such that $G$ admits a zero-sum $h$-magic labeling. \\ % Clearly, if a graph is $h$-magic, it is not necessarily $k$-magic (for $h \neq k$). %and this condition is called {\it zero-sum $h$-magic rule} Recently, Choi, Georges and Mauro in \cite{cho} proved that if $G$ is $3$-regular graph, then $N(G)$ is $\mathbb{N} \setminus \{2\}$ or $\mathbb{N} \setminus \{2,4\}$. In this article, we extend this result by showing 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$ ($r\neq 5$) is odd and $G$ is a $2$-edge connected $r$-regular graph, then $ N(G)=\mathbb{N} \setminus \{2\}$.\\ The original concept of $A$-magic graph is due to J. Sedlacek \cite{seed}, who defined it to be a graph with a real-valued edge labeling such that have distinct non-negative labels, and, in the manner described above, the sum of the labels of the edges incident to vertex $v$ is constant over $V(G)$. Stanley considered $\mathbb{Z}$-magic graphs and showed that the theory of magic labeling can be put into the more general context of linear homogeneous diophantine equations, \cite{stan,stan1}. Recently, there have been considerable research articles in graph labeling. Interested readers are referred to \cite{gall,salehi, salehi1,salehi2,wall}.\\ In \cite{salehi}, the null set of some classes of regular graphs are determined. \begin{thm} \textit{If $n \geq 4$, then $N(K_n) = \left\{ \begin{array}{ll} \mathbb{N}, & \hbox{if n is odd;}\\ \mathbb{N} \setminus \{2\}, & \hbox{if n is even.} \end{array} \right. $} \end{thm} \begin{thm} \textit{ $N(C_n) = \left\{ \begin{array}{ll} \mathbb{N}, & \hbox{if n is even;} \\ 2\mathbb{N} , & \hbox{if n is odd.} \end{array} \right. $} \end{thm} Recently, the following theorem was proved, in \cite{akb2} and \cite {km}. \begin{thm}\label{reg} \textit{Let $r\geq 3$ be a positive integer. Then every $r$-regular graph admits a zero-sum $5$-flow.} \end{thm} This theorem implies that if $G$ is an $r$-regular graph ($ r \geq 3$), then $\mathbb{N}\setminus \{2,3,4\} \subseteq N(G)$. Before establishing our results we need some theorems. \begin{thm}{\rm\cite{kano}}\label{kan} \textit{Let $r \geq 3$ be an odd integer and let $k$ be an integer such that $1 \leq k \leq \frac{2r}{3}$. Then every $r$-regular graph has a $[k-1, k]$-factor each component of which is regular.} \end{thm} Also, the following theorems were proved. \begin{thm}{\rm \cite[p.179] {ketabk}}\label{ka} \textit{Let $r \geq 3$ be an odd integer, and $G$ be a $2$-edge connected $[r - 1, r]$-multigraph having exactly one vertex $w$ of degree $r - 1$. Then for every even integer $k$, $2 \leq k \leq \frac{2r}{3}$, $G$ has a $k$-factor. %$(ii)$ for every odd integer $h'$, $\frac{r}{3} \leq h' \leq r$, $G$ has a $[h' -1, h']$-factor $F$ such %that $d_F (w) = h'- 1$ and $d_F (x) = h'$, for every $x \in V (G) \setminus \{w\}$. } \end{thm} \begin{thm}{\rm \cite{ba}} \label{d}\textit{Every $2$-edge connected $(2r+1)$-regular multigraph contains a $2$-factor.} \end{thm} \begin{thm}{\em \cite{handbook}}\label{peterson} \textit{ Every $2r$-regular multigraph admits a $2$-factorization.} \end{thm} % %In the following example, we show that the converse of Part $(ii)$ of Theorem \ref{tii} is not correct. %Let $H= W_{n+1}$, where $ n\geq 3$ and $ n\neq 0$ (mod $3$). It is not hard to see that for each edge $e$ of %$H$, $H \setminus \{e\}$ is not bipartite and also $H$ does not admit a zero-sum $3$-magic. \section{Regular Graphs} Let $G$ be an $r$-regular graph. In this section we prove that for every even natural number $r$ ($r>2$), $N(G)= \mathbb{N}$ and for every odd natural number $r$ ($r \neq 5$), $\mathbb{N}\setminus \{2,4\} \subseteq N(G)$.\\ We start this section with the following theorem. \begin{thm}\label{fard} \textit{Let $r$ be an odd integer and $r \geq 3$. Then every $r$-regular multigraph with at most one cut-edge admits a zero-sum $4$-magic labeling. } \end{thm} \begin{proof}{Obviously, we may suppose that $G$ is connected. First assume that $G$ is a $2$-edge connected $r$-regular multigraph. By Theorem \ref{d}, $G$ has a $2$-factor, say $H$. Now, assign $1$ and $2$ to the edges of $H$ and the edges of $G\backslash E(H)$, respectively. It is not hard to see that $G$ admits a zero-sum $4$-magic labeling.\\ Now, suppose that $G$ has a cut-edge, say $e$. Let $G'=G\setminus \{e\}$. Clearly, $G'$ has two components, say $G_1$ and $G_2$. Since both $G_1$ and $G_2$ are $2$-edge connected $[r - 1, r]$-multigraphs, by Theorem \ref{ka}, $G_1$ and $G_2$ have $2$-factors and so $G$ has a $2$-factor. Hence by the same argument as we did before, $G$ has a zero-sum $4$-magic labeling.} %Now, suppose that $G$ has a cut-edge, say $uv$. Let $G'=G\setminus \{uv\}$. Clearly, $G'$ has two components, say $G_1$ and $G_2$. Assume that $u \in V(G_1)$ %and $v\in V(G_2)$. Now, consider $G_1$. Note that $G_1$ is a $2$-edge connected $[r - 1, r]$-multigraph which $u$ is the only vertex of $G_1$ of degree $r-1$. %By Theorem \ref{ka}, $G_1$ has a $2$-factor, say $H$. Now, define a function $l: E(G_1) \rightarrow %\{1,2\}$, where $l(e)=1$ for every $e\in E(H)$ and $l(e)=2$ for every $e \in E(G_1) \setminus E(H)$. Then $s(u)=2$ and $s(x)=0 $ (mod $4$), for every $x \in V %(G_1) \setminus \{u\}$. By a similar argument one can obtain an edge labeling for $G_2$ with values $1$ and $2$ such that $s(v)=2$ and $s(x)=0 $ (mod $4$), %for every $x \in V (G_2) \setminus \{v\}$. Now, define $l(uv)=2$. Clearly, we obtain a zero-sum $4$-magic and we are done. \end{proof} \begin{rem}\label{zoj} {\rm If $G$ is a $2r$-regular multigraph, then by assigning $2$ to all edges of $G$, one can obtain a zero-sum $4$-magic labeling. } \end{rem} The following remark shows that there are some regular graphs with no zero-sum $4$-magic labeling. \begin{rem} \textit{Let $r$ be an odd integer ($r \geq 3$) and $G$ be an $r$-regular multigraph. If there is a vertex $u$ such that every edge adjacent to $u$ is a cut-edge, then $G$ does not admit a zero-sum $4$-magic labeling. } \end{rem} \begin{proof}{For contradiction assume that $G$ admits a zero-sum $4$-magic labeling, say $l$. Since $G$ admits a zero-sum $4$-magic labeling it is not hard to see that there exists at least one edge adjacent to $u$, say $uv$, with label $1$ or $3$. Assume that $G'$ is the connected component of $G\setminus \{u\}$ containing $v$. Clearly, we have $\sum_{x \in V(G')}s(x)= 2\sum_{e \in E(G')}l(e)+l(uv)$. But $\sum_{x \in V(G')}s(x)=0$ (mod $2$). On the other hand, $2\sum_{e \in E(G')}l(e)+l(uv)=1$ (mod $2$), a contradiction.} \end{proof} %Let $G$ be a connected $\{1,7\}$-multigraph with order at least 3. Suppose that every cut-edge is a pendant edge of and the induced subgraph on all vertices of degree 7 has no cut-edge. Then if $h$ is a fixed pendant edge of $G$, there exists a function $l$ from $E(G)$ into $\{1,2\}$ such that $l(h)=a$ and for every vertex $v$ in $V(G)$, the zero-sum 3-magic rule holds in $v$ under $l$. \begin{lem}\label{7} \textit{Let $G$ be a $\{1,7\}$-multigraph with no component that is isomorphic to $K_2$. Suppose that the subgraph induced by the set of vertices of degree $7$ has no cut-edge. Fix $a \in \{1,2\}$. Then if $h$ is a fixed pendant edge of $G$, then there exists a function $l$ from $E(G)$ into $\{1,2\}$ such that $l(h)=a$ and for every vertex $v$ of degree $7$ in $V(G)$, the zero-sum $3$-magic rule holds in $v$ under $l$. }\end{lem} \begin{proof}{First assume that $a=1$ and $G$ is a multigraph with exactly one pendant edge $h=uv$. Assume that $d_G(v)=1$. Let $G'=G\setminus \{v\}$. Note that $G'$ is a $2$-edge connected $[6, 7]$-multigraph in which $u$ is the only vertex of degree $6$. By Theorem \ref{ka}, $G'$ has a $2$-factor $H$. Define $l(e)=2$, for every $e\in E(H)$ and define $l(e)=1$, for every $e \in E(G') \setminus E(H)$. Hence we obtain the desired labeling for $G$.\\ \noindent Now, for $a=2$, we define $l^*$ to be the labeling defined as above, and let $l=2l^*$ (mod 3).\\ Next, suppose that the number of pendant edges of $G$ is at least two and $a=1$. Consider two copies of $G$, say $G_1$ and $G_2$. Assume that $u_iv_i$, $1 \leq i \leq k $ ($k \geq 2$) are all edges of $G_1$, such that $u_i, v_i \in V(G_1)$ and $d_{G_1}(v_i) = 1$. Also, suppose that $u'_i$ and $v'_i$ are the vertices corresponding to $u_i$ and $v_i$ ($i = 1, \ldots , k$) in $G_2$. Let $G^*$ be the multigraph obtained by removing the vertices $v_1,\ldots , v_k$ and $v'_1, \ldots , v'_k$ and joining $u_i$ and $u'_ i$ in $G_1\cup G_2$, for $i = 1, \ldots , k$. Since none of the connected components of $G$ is $K_2$, $G^*$ is a $2$-edge connected $7$-regular multigraph. Thus by Theorem \ref{d}, $G^*$ has a $2$-factor, say $H$. If the edge in $G^*$ corresponding to $h$ belongs to $ E(H)$, then let $l(e)=2$ for every $e \in E(G^*) \setminus E(H)$ and $l(e)= 1$ for every $e\in E(H)$. Otherwise, define $l(e)=1$ for every $e \in E(G^*) \setminus E(H)$ and $l(e)=2$ for every $e\in E(H)$. Hence we obtain the desired labeling.\\ Now, for $a=2$, we define $l^*$ to be the labeling defined as above, and let $l=2l^*$ (mod 3), we obtain the desired labeling and the proof is complete.} \end{proof} In the following theorem, we prove that for every $r$-regular graph $G$ ($r \geq 3$, $r \neq 5$), $3\in N(G)$. \begin{thm}\label{r} \textit{Let $r$ be an integer such that $r \geq 3$ and $r\neq 5$. Then every $r$-regular graph admits a zero-sum $3$-magic labeling. } \end{thm} \begin{proof}{First assume that $r$ is an even positive integer and $r\neq2$. The proof is by induction on $r$. If $r=4$, then by Theorem \ref{peterson}, $G$ is decomposed into $2$-factors $G_1$ and $G_2$. Now, assign $1$ and $2$ to all edges of $G_1$ and $G_2$, respectively. Thus $G$ admits a zero-sum $3$-magic labeling. If $r=6$, then assign $1$ to the edges of $G$ to obtain a zero-sum $3$-magic labeling. Now, suppose that $r \geq 8$. So, by Theorem \ref{peterson}, $G$ is decomposed into $2$-factors. Choose two $2$-factors $G_1$ and $ G_2$. Now, by induction hypothesis $G \setminus (E(G_1)\cup E(G_2))$ admits a zero-sum $3$-magic labeling. On the other hand, by the case $r=4$, $G_1 \cup G_2$ admits a zero-sum $3$-magic labeling and the proof is complete.\\ Now, assume that $r$ is an odd positive integer. If $r$ is divisible by $3$, then assign $1$ to all edges of $G$ to obtain a zero-sum $3$-magic labeling.\\ If $r$ is not divisible by $3$, then $r \equiv 1,5,7,11$ (mod $12$).\\ \noindent First, suppose that $r=7$. For finding a zero-sum $3$-magic labeling we construct a rooted tree $T$ from $G$, where every maximal $2$-edge connected subgraph of $G$ is considered as a vertex of $T$ and every edge of $T$ is corresponding to a cut-edge of $G$. Now, by traversing $T$, level by level, we find a zero-sum $3$-magic labeling for $G$. We start from the root of $T$ say $H$ (The root can be taken to be any vertex). Let $h$ be an arbitrary cut-edge incident with $H$. Assign the label 1 to $h$. By Lemma \ref{7}, one can assign $1$ or $2$ to each edge of $H$ and cut-edges of $G$ which are incident with $H$ such that every cut-edge of $G$ incident with $H$ has value $1$ or $2$ and moreover the zero-sum $3$-magic rule holds in every vertex of $H$. Now, we move to the next vertex level of $T$. Let $H'$ be a vertex adjacent to $H$ in $T$. At this stage there exists just one cut-edge of $G$ incident with $H'$ which has been labeled by $1$ or $2$. Now, by Lemma \ref{7}, we can label each edge of $H'$ and each cut-edge of $G$ that is incident to $H'$ (except $h$ which is already labeled 1 or 2) with 1 or 2 such that the zero-sum 3-magic rule holds in every vertex of $H'$. By continuing this procedure we obtain a zero-sum $3$-magic labeling for $G$, as desired.\\ \noindent Now, assume that $r=11$. Then by Theorem \ref{kan}, $G$ has a $[6, 7]$-factor, say $H$ whose components are regular. Let $H_1$ and $H_2$ be the union of $6$-regular components and $7$-regular components of $H$, respectively. Also, by Theorem \ref{peterson}, $H_1$ is decomposed into $2$-factors $G_1, G_2$ and $G_3$. Now, assign $2$ to all edges of $H_2$, $G_1$ and $G_2$ and assign $1$ to the edges of $G\setminus (E(H_1) \cup E(H_2))$ and $G_3$. Then it is not hard to see that $G$ admits a zero-sum $3$-magic labeling.\\ \noindent Now, suppose that $r=12k+1$ or $r=12k+7$, and $k\geq 1$. By Theorem \ref{kan}, $G$ has a $[6k-2, 6k-1]$-factor, say $H$, whose components are regular. Let $H_1$ and $H_2$ be the union of $(6k-2)$-regular components and $(6k-1)$-regular components of $H$, respectively. Since $6k-2$ is even, $H_1$ admits a zero-sum $3$-magic labeling. Now, assign $2$ to the edges of $H_2$ and assign $1$ to all edges of $G\setminus (E(H_1) \cup E(H_2))$. Then $G$ admits a zero-sum $3$-magic labeling.\\ \noindent Now, assume that $r=12k+5$ or $r=12k+11$, and $k\geq 1$. By Theorem \ref{kan}, $G$ has a $[6k+1, 6k+2]$-factor, say $H$, whose components are regular. Let $H_1$ and $H_2$ be the union of $(6k+1)$-regular components and $(6k+2)$-regular components of $H$, respectively. Since $6k+2$ is even, $H_2$ admits a zero-sum $3$-magic labeling. Now, assign $2$ to all edges of $H_1$ and assign $1$ to all edges of $G\setminus (E(H_1) \cup E(H_2))$. Therefore, $G$ admits a zero-sum $3$-magic labeling, as desired.} \end{proof} Now, we are in a position to prove our main theorem for regular graphs.\\ \begin{thm}\label{main} \textit{Let $G$ be an $r$-regular graph ($r \geq 3$, $r\neq5$). If $r$ is even, then $ N(G)=\mathbb{N}$, otherwise $\mathbb{N} \setminus \{2,4\}\subseteq N(G)$. } \end{thm} \begin{proof} {First, assume that $r$ is even. Clearly, by assigning $1$ to all edges of $G$, it is seen that $2 \in N(G)$. Moreover, Theorem \ref{reg} immediately follows, $k \in N(G)$ for $ k \geq 5$ and $k=1$. By Theorem \ref {r} and Remark \ref{zoj}, $ N(G)$ contains 3 and 4 as well, giving the result. Next, assume that $r$ is an odd integer. Then by Theorems \ref{reg} and \ref{r} we are done.}\end{proof} \begin{lem} \textit{If $r$ {\rm($r\neq 5$)} is odd and $G$ is a $2$-edge connected $r$-regular graph, then $ N(G)=\mathbb{N} \setminus \{2\}$.} \end{lem} \begin{proof}{Since the degree of each vertex is odd, $2 \not \in N(G)$. Now, the result follows from Theorems \ref{reg}, \ref{fard} and \ref {r}. } \end{proof} We close this section with the following conjecture. \begin{conj} \textit{Every $5$-regular graph admits a zero-sum $3$-magic labeling.} \end{conj} It is easily seen that a $5$-regular graph $G$ admitting a zero-sum $3$-magic labeling is equivalent to $G$ having a factor with the degree sequence $1$ or $4$. \section{Bipartite Graphs} In this section we show that if $G$ is a $2$-edge connected bipartite graph, then $\mathbb{N} \setminus \{2,3,4,5\} \subseteq N(G)$. Before establishing this result we need some definitions and theorems.\\ Let $G$ be a directed graph. A {\it $k$-flow} on $G$ is an assignment of integers with maximum absolute value at most $k- 1$ to each edge of $G$ such that for each vertex of $G$, the sum of the labels on incoming edges is equal to that of the labels on outgoing edges. A {\it nowhere-zero $k$-flow} is a $k$-flow with no zeros.\\ A {\it $\mathbb{Z}_k$-flow} on $G$ is an assignment of element of $\mathbb{Z}_k$ to each edge of $G$ such that for any vertex of $G$, the sum of the labels on incoming edges is equal to that of the labels on outgoing edges (mod $k$). A {\it nowhere-zero $\mathbb{Z}_k$-flow} is a $\mathbb{Z}_k$-flow with no zero, for every $k \in \mathbb{N}$.\\ The following theorem was proved in \cite{sey1}. \begin{thm} \label{sey} \textit{Every $2$-edge connected directed graph admits a nowhere-zero $6$-flow.} \end{thm} The following well-known theorem is due to Tutte. \begin{thm}{\rm \cite[p.294] {lov}} \label{tutt} \textit{If $G$ is a directed graph and $k \geq 1$ is an integer, then $G$ admits a nowhere-zero $k$-flow if and only if $G$ admits a nowhere-zero $\mathbb{Z}_k$-flow.} \end{thm} In \cite{salehi}, the null set of a complete bipartite graph was determined. \begin{thm} \label{sal} \textit{If $m,n \geq 2$, then $N(K_{m,n}) = \left\{ \begin{array}{ll} \mathbb{N}, & \hbox{if m+n is even;}\\ \mathbb{N} \setminus \{2\}, & \hbox{if m+n is odd.} \end{array} \right. $} \end{thm} In the following theorem we determine a necessary condition for the existence of a zero-sum $h$-magic labeling in bipartite graphs. \begin{thm} \label{tii} \textit{Let $G$ be bipartite in which $G$ admits a zero-sum $h$-magic labeling, for some $h \in \mathbb{N}$. Then $G$ is $2$-edge connected. } \end{thm} \begin{proof}{ Assume that $G$ admits a zero-sum $h$-magic labeling, say $l$. To the contrary, let $e=uv$ be a cut-edge of $G$. Note that $G\setminus \{e\}$ is bipartite graph. Let $H$ be one of the connected components of $G \setminus \{e\}$ with two parts $X$ and $Y$ such that $Y \cap \{u,v\} \neq \emptyset$. It is not hard to see that in $G$, $\sum_{x\in X}s(x)=\sum_{y\in Y}s(y)-l(uv)$. On the other hand, by assumption $$\sum_{x\in X}s(x)=\sum_{y\in Y}s(y)\equiv 0 \,\,({\rm mod} \,\,h).$$ This implies that $l(uv)\equiv 0$ (mod $h$), which is a contradiction. } \end{proof} Next, we determine the null set of a $2$-edge connected bipartite graph. \begin{thm}\label{bipar} \textit{Let G be a $2$-edge connected bipartite graph. Then $G$ admits a zero-sum $k$-magic labeling, for $k \in \mathbb{N} \setminus \{2,3,4,5\}$.} \end{thm} \begin{proof} { First, orient all edges from one part of $G$ to the other part and call the resultant directed graph by $G'$. By Theorem \ref{sey}, $G'$ admits a nowhere-zero $6$-flow. Thus $G'$ admits a nowhere-zero $k$-flow, for every $k \in \mathbb{N}\setminus\{2,3,4,5\}$ and so by Theorem \ref{tutt}, $G'$ admits a nowhere-zero $\mathbb{Z}_k$-flow, for $k \in \mathbb{N}\setminus \{2,3,4,5\}$. Now, by removing the direction of all edges we conclude that $G$ admits a zero-sum $k$-magic labeling, for every $k \in \mathbb{N}\setminus\{2,3,4,5\}$ and the proof is complete.} \end{proof} In the following remark, we show that there are some $2$-edge connected bipartite graphs with no zero-sum $k$-magic labeling, for $k=2,3,4$. %First note that the existence of nowhere-zero $k$-flow is equitable by zero-sum $k$-flow in bipartite graph and so it is equitable by zero-sum $k$-magic. Because one can orient all edges from one part of graph to the other part. \begin{rem} {\rm In a bipartite graph the existence of a zero-sum $k$-flow is equivalent to the existence of a zero-sum $k$-magic labeling. To see this first orient all edges from one part to the other part and call the directed graph by $G'$. Therefore, $G'$ admits a nowhere-zero $k$-flow. Now, by removing the direction of all edges we conclude that $G$ admits a zero-sum $k$-flow. So, $G$ admits a zero-sum $k$-flow if and only if $G'$ admits a nowhere-zero $k$-flow. Thus by Theorem \ref{tutt}, $G'$ admits a nowhere-zero $\mathbb{Z}_k$-flow. But the later condition implies that $G$ admits a zero-sum $k$-magic labeling.\\ Let $G$ be the following graph. By a computer search one can see that $G$ does not admit a zero-sum $4$-flow, see \cite{ak}. So $G$ does not admit a zero-sum $4$-magic labeling.\\ Since $G$ does not admit a zero-sum $4$-flow, $G$ does not admit a zero-sum $k$-flow, for $k \leq 4$. Hence $G$ does not admit a zero-sum $k$-magic labeling, for $k=2,3,4$.\\ \vspace{4cm} \special{psfile=bii.eps hscale=70 vscale=75 hoffset=120 voffset=-510} \vspace{0cm}} \end{rem} % %\begin{remark} \textit{For every integer $k$, there is a graph with minimum degree $k$, which does not admits a zero-sum $3$-magic.} %\end{remark} %\begin{proof}{Let $G$ be a bipartite graph with two Parts $X$ and $Y$, where there is a vertex $x\in V(X)$ such that $d_G(x)=k$. Assume that $\{u, v\} \in Y$. Let $G'= G \cup \{uv\}$. Clearly, $d_G'(x)=k$. We claim that $G'$ does not admit a zero-sum $3$-magic. By contrary assume that $G'$ admits a zero-sum $3$-magic. Then in $G$, $\sum_{x\in X}l^+(x)=\sum_{y\in Y}l^+(y)$. On the other hand, by assumption $\sum_{x\in X}l^+(x)=0$, (mod $3$) and this implies that $l(uv)=0$, which is contradiction.} %\end{proof} \noindent {\bf Acknowledgements.} The first and the third authors are indebted to the School of Mathematics, Institute for Research in Fundamental Sciences (IPM) for the support. The research of the first author and the third author were in part supported by a grant from IPM (No.92050212) and (No.92050015), respectively. Also, the authors would like to express their deep gratitude to Somayeh Moazzeni and Fatemeh Khaghanpour for very careful reading of the paper and their valuable comments. Finally, the authors are very grateful to the referees for their appropriate and constructive suggestions for improving the paper. \begin{thebibliography}{mm} \bibitem{ak} S. Akbari, A. Daemi, O.Hatami, A. Javanmard, A. Mehrabian, Zero-sum flows in regular graphs, Graphs and Combinatorics 26 (2010), 603 -615. \bibitem{akb2} S. Akbari, N. Gharghani, G.B. Khosrovshahi, S. Zare, A note on zero-sum $5$-flow in regular graphs, The Electronic Journal of Combinatorics 19(2), 2012, \#P$7$. \bibitem{km} S. Akbari, M. Kano, S. Zare, $0$-Sum and $1$-Sum Flows in Regular Graphs, submitted. %\bibitem{bondy} % J.A. Bondy aBnd U.S.R. Murty, Graph Theory with Applications, North Holland, New York, 1976. %\bibitem{akb3} S. Akbari, N. Gharghani, G.B. Khosrovshahi, A. Mahmoody, On zero-sum $6$-flows of graphs, Linear Algebra and its Applications 430 (2009) 3047--3050. \bibitem{ketabk} J. Akiyama and M. Kano, Factors and Factorizations of Graphs, Springer, 2007. \bibitem{ba} F. B{\rm $\ddot{a}$}bler, {\rm $\ddot{U}$}ber die zerlegung regul{\rm $\ddot{a}$}rer Streckencomplexe ungerader Ordnung, Comment. Math. Helv. 10 (1938), 275--287. \bibitem{cho} J.-.O, Choi, J.P. Georges, D. Mauro, On zero-sum $\mathbb{Z}_k$-magic labelings of $3$-regular graphs, Graphs and Combinatorics, 29 (2013), no. 3, 387-398. \bibitem{gall} J. Gallian, A dynamic survey in graphs labeling (ninth edition), Electronic Journal of Combinatorics (2005). %\bibitem{kann} M. Kano, $[a, b]$-factorization of a graph. J. Graph Theory 9 (1985) 129�- %146. \bibitem{lov} R.L. Graham, M. Gr{\rm$\ddot{o}$}tschel and L. Lov{\rm$\acute{a}$}sz, Handbook of Combinatorics, The MIT Press-North-Holland, Amesterdam (1995). \bibitem{kano} M. Kano, Factors of regular graph, J. Combin. Theory Ser. B 41 (1986), 27-36. \bibitem{handbook} J. Petersen, Die Theorie der regularen Graphen, Acta Math(15) (1891), 193--220. \bibitem{salehi} E. Salehi, Zero-sum magic graphs and their null sets, Ars Combinatoria 82 (2007), 41-53. \bibitem{salehi1} E. Salehi, On Zero-Sum Magic Graphs and Their Null Sets, Bulletin of the Institute of Mathematics, Academia Sinica 3 (2008), 255-264. \bibitem{salehi2} E. Salehi, and S. Hansen, Zero-Sum Magic and Null Sets of Planar Graphs, to appear in the Congressus Numerantium 72 (2010), 55-64. \bibitem{seed} J. Sedlacek, On magic graphs, Math. Slov. 26 (1976), 329-335. %\bibitem{seed1} J. Sedlacek, Some properties of magic graphs, in graphs, hypergraph, Bloc Syst. (1976) Proc. Symp. Comb. \bibitem{sey1} P.D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981), 130-135. \bibitem{stan} R.P. Stanley, Linear homogeneous diophantine equations and magic labelings of graphs, Duke Mathematics Journal 40 (1973), 607-632. \bibitem{stan1} R.P. Stanley, Magic labeling of graphs, symmetric magic squares, systems of parameters and Cohen- Macaulay rings, Duke Mathematics Journal 40 (1976), 511-531. \bibitem{wall} W.D. Wallis, Magic Graphs, Birkhauser Boston (2001). \end{thebibliography} \end{document}