% 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}
