% 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{\bf\Large  A note on zero-sum $5$-flows in regular  graphs}



\author{{}\\{}\\
{\normalsize{\sc S. Akbari\,${}^{a, b}$, N. Ghareghani\,${}^{ d, b}$,
G. B. Khosrovshahi\,${}^{b, e}$, S. Zare\,${}^{c}$}}
\\{\footnotesize{\it ${}^{a}$Department of
Mathematical Sciences, Sharif University of Technology}}
\\{\footnotesize{\it ${}^{b}$School of Mathematics, Institute for Research in Fundamental Sciences {\rm (IPM)}}}
\\{\footnotesize{\it P.O. Box 19395-5746}}
\\{\footnotesize{\it ${}^{c}$ Department of
Mathematical Sciences, Amirkabir University of Technology}}
\\{\footnotesize{\it ${}^{d}$ Department of Engineering Science, College of Engineering, University of Tehran}}
\\{\footnotesize {\it P.O. Box 11165-4563, Tehran, Iran}}
\\{\footnotesize{\it ${}^{e}$ Department of
Mathematics, University of Tehran}}
\thanks{{\it E-mail addresses}: $\mathsf{s\_akbari@sharif.edu}$
(S. Akbari), $\mathsf{ghareghani@ipm.ir}$ (N. Ghareghani), $\mathsf{
rezagbk@ipm.ir }$ (G.B. Khosrovshahi),
$\mathsf{sa\_zare\_f@yahoo.com}$ (S. Zare).}
\thanks {Keywords: Zero-sum flow, regular graph.}
\thanks {AMS (2010) { \it Subject classification}: 05C21, 05C22.}
\thanks {Corresponding author: G.B. Khosrovshahi.}}
\date{}
%\begin{document}
\maketitle
\begin{abstract}
Let $G$ be a graph. A {\it zero-sum flow} of $G$ is an assignment
of non-zero real numbers to the edges of $G$ such that the sum of the
values of all edges incident with each vertex is zero. Let $k$ be
a natural number. A {\it zero-sum $k$-flow} is a flow with values
from the set \mbox{$\{\pm 1,\ldots ,\pm(k-1)\}$}. It has been
conjectured that every $r$-regular graph, $r\geq 3$, admits a zero-sum
$5$-flow. In this paper we provide an affirmative answer to this
conjecture, except for  $r=5$.
\end{abstract}
%Abstract----------------------------------------------------------------------------------------





\date{}







\vspace{9mm} \noindent{\bf\large 1. Introduction}\vspace{5mm}





Nowhere-zero flows on graphs were introduced by Tutte \cite{tut} in
1949 and since then have been extensively studied by many
authors.  A great deal of research in the area has been motivated
by Tutte's 5-Flow Conjecture  which states that every $2$-edge connected
graph can have its edges directed and labeled by integers from
$\{1, 2, 3, 4\}$ in such a way that Kirchhoff’s current law is
satisfied at each vertex. In 1983,  Bouchet \cite{bouchet}
generalized this concept to bidirected graphs. A \emph{bidirected graph} $G$ is a graph with vertex set $V(G)$
and edge set $E(G)$ such that each edge is oriented as one of
the four possibilities: %\setlength{\unitlength}{0.35mm}
$$\begin{picture}(45,5)(0,-2)
\thicklines
\put(15,0){\vector(-1,0){4}}\put(27,0){\vector(1,0){4}}
\thinlines \put(0,0){\line(1,0){40}} \put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\end{picture},\,\,
\begin{picture}(45,5)(0,-2)
\thicklines \put(15,0){\vector(1,0){4}}\put(27,0){\vector(1,0){4}}
\thinlines \put(0,0){\line(1,0){40}} \put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\end{picture},\,\,
\begin{picture}(45,5)(0,-2)
\thicklines
\put(15,0){\vector(1,0){4}}\put(27,0){\vector(-1,0){4}}
\thinlines \put(0,0){\line(1,0){40}} \put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\end{picture},\,\,
\begin{picture}(45,5)(0,-2)
\thicklines
\put(15,0){\vector(-1,0){4}}\put(27,0){\vector(-1,0){4}}
\thinlines \put(0,0){\line(1,0){40}} \put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\end{picture}.$$
 Let $G$ be a bidirected graph. For every $v \in V(G)$, the
set of all edges with tails (respectively, heads) at $v$ is denoted by
$E^+(v)$ (respectively, $E^-(v)$). The function $f:E(G) \longrightarrow
\mathbb{R}$ is a \emph{bidirected flow} of $G$ if for every $v
\in V(G)$, we have
$$\sum_{e \in E^+(v)} f(e) = \sum_{e \in E^-(v)} f(e).$$ If $f$ takes its values from the set \mbox{$\{\pm 1,\ldots ,\pm(k-1)\}$}, then it is called a \emph{nowhere-zero bidirected $k$-flow}.\\


 Bouchet proposed the following interesting  conjecture. \\

\noindent {\bf Bouchet's Conjecture.} {\rm \cite{bouchet, xui}}
\textit{Every bidirected graph that has a nowhere-zero bidirected
flow admits a nowhere-zero bidirected $6$-flow.}\\

Bouchet showed that his conjecture is true if $6$ is replaced by
$216$. Then Zyka  \cite{zyk} reduced $216$ to $30$. Also, DeVos proved Bouchet's Conjecture with 6 replaced by 12, see \cite{devos}.


Let $G$ be a graph.  A {\it
$k$-regular} graph is  a graph where each vertex is of degree $k$. A {\it zero-sum flow} of $G$ is an assignment of non-zero real numbers
to the edges  of $G$ such that the sum of the values of all edges
incident with each vertex is zero. Let $k$ be a natural number. A {\it zero-sum $k$-flow} is a
flow with values from the set \mbox{$\{\pm 1,\ldots
,\pm(k-1)\}$}. The following conjecture was posed on the zero-sum flows in graphs.\\


\noindent{\bf Zero-Sum Conjecture (ZSC).} {\rm \cite{zerosum1}}   \textit{If $G$ is a graph
with a zero-sum flow, then $G$ admits a zero-sum $6$-flow.}\\

The following theorem shows the relation between Bouchet's Conjecture and ZSC.

\begin{thm} {\em \cite{d}}\label{bou}{ \textit Bouchet's Conjecture
and ZSC are equivalent.}
\end{thm}


The following conjecture is a stronger version of ZSC for regular graphs.\\


\noindent{\bf  Conjecture A.}   {\rm \cite{d}}  \textit{ Every $r$-regular graph ($r\geq 3$)
admits a zero-sum $5$-flow.}\\

\noindent Motivated by Bouchet's Conjecture and along with Theorem \ref{bou}
we focused our attention to establish the Conjecture A. In the next section, except for the case $r = 5$, we prove Conjecture A.
The following two results show the validity of this conjecture for some special cases.
%Recently, in  connection with this conjecture the following two theorems were proved.

\begin{thm}{ \em \cite{zerosum1}} \label{evenreg}
 \textit{ Let $r$ be an even integer with $r\geq 4$. Then every
$r$-regular graph has a zero-sum $3$-flow.}
\end{thm}

\begin{thm}{ \em \cite{d}}\label{3reg}  \textit{ Let $G$ be an $r$-regular graph.
If  $r$ is divisible by $3$, then  $G$ has a zero-sum $5$-flow.}
\end{thm}

\noindent {\bf Remark.} There are some regular graphs with no zero-sum $4$-flow. To see this
consider the graph given in Figure $1$. Assume, to the contrary, that this  graph has a zero-sum $4$-flow. Since
the sum of the values of all three edges incident with a vertex is zero, not all can be odd, so $-2$ or $2$ should appear on (exactly) one edge incident to the vertex.  On the other hand two numbers with absolute
value $2$ cannot appear in the neighborhood of a vertex. So the edges of $G$ with values $\pm 2$
form a perfect matching. But by a celebrated  Theorem of Tutte \cite[p.76] {bondy}, $G$ has no  perfect matching, a contradiction.


\vspace{3cm} \special{psfile=3r.eps hscale=40 vscale=40 hoffset=90
voffset=-220} \vspace{4cm} \vspace{-2.5cm}$$\textmd{Figure $1$. A $3$-regular graph with no zero-sum $4$-flow}$$\\








\vspace{9mm} \noindent{\bf\large 2. The Main Result }\vspace{5mm}


In this section we prove that every $r$-regular graph, $r\geq 3$,
$r\neq 5$, admits a zero-sum $5$-flow. Before establishing our main
result we need some notations and definitions.


A {\it factor} of a graph is a spanning subgraph. A {\it$k$-factor} is a factor which is $k$-regular. In particular a
$2$-factor is a disjoint union of cycles that cover
all the vertices. Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A {\it $k$-factorization} of $G$ is a partition of  the edges of $G$ into disjoint $k$-factors.
For integers $a$ and $b$, $1 \leq a \leq b$, an {\it $[a, b]$-factor} of
$G$ is defined  to be a factor $F$ of $G$ such that
$a \leq d_F (v) \leq b$, for every  $v \in V (G)$.    For any vertex $v\in V(G)$, let
$N_{G}(v)=\{\,u \in V(G)\,|\,uv\in E(G)\,\}$.\\


%The following  theorem is also needed.
Below we state two known theorems about the factorization of graphs.

\begin{thm}{ \em \cite{handbook}}\label{peterson}
\textit{Every $2k$-regular multigraph admits a $2$-factorization.}
\end{thm}

\begin{thm}{ \em \cite{kano}}\label{kano}
\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}






\begin{lem}\label{qr}
\textit{Let  $G$ be an $r$-regular graph. Then
for every even integer $q$, $ 2r \leq q \leq 4r$, there exists
a function $f: E(G) \rightarrow \{2, 3, 4\}$ such that for every
$u \in V(G)$, $\sum_{v \in N_G(u)}f(uv)=q$.}
\end{lem}
\begin{proof}
{For every edge $e=uv$, we add a new edge $e'=uv$ to the graph $G$ and call the resulting graph  $G'$.
%We  duplicate   edges and joining the same pair of vertices of $G$ and call the resultant graph by $G'$.
Clearly, $G'$ is a $2r$-regular
 multigraph. By Theorem \ref{peterson}, $G'$ admits   a $2$-factorization  with $2$-factors $F_1, \ldots, F_{r}$.
Now,  for every $e \in F_i$, $1 \leq i \leq r$, we define a  function $g: E(G') \rightarrow \{1,2\}$ as
follows:


$$g(e)=\left\{
  \begin{array}{ll}
     2, & \hbox{$1 \leq i \leq  \frac{q-2r}{2}$;}\\
 1, & \hbox{$ \frac{q-2r}{2}<i$.}

  \end{array}
\right.$$

Therefore,   for each  $u
\in V(G')$, $\sum_{v \in N_{G'}(u)}g(uv)=q$. Now,  define a function $f: E(G) \rightarrow \{2,3,4\}$ such that
for every $e=uv \in E(G)$, $f(e)= g(e)+g(e')$, where $e'=uv$ in $G'$.
Then for every $u \in V(G)$,    $\sum_{v \in N_G(u)}f(uv)=q$, as desired. }
\end{proof}
%Also, we propose an interesting theorem which states that:

Now, we are in a position to prove our main theorem.



\begin{thm}
\textit{Let $r \geq 3$ and $r \neq 5$. Then
every $r$-regular graph has a zero-sum $5$-flow.}
\end{thm}

\begin{proof}
{
%First consider the case when $r$ is an even integer, then the
%result follows by Theorem 3 in \cite{zerosum1}. For $r=3$ the
%result follows by \cite[Theorem 2]{zerosum1}.
If $r=3$, then by Theorem \ref{3reg}, the assertion holds. First we prove the theorem for  $r=7$. Let $G$ be a $7$-regular
graph. Then, by Theorem \ref{kano}, $G$ is a disjoint union of a $3$-regular graph $H_1$ and a $4$-regular graph $H_2$.   By Theorem \ref{peterson}, $H_2$
can be decomposed into two $2$-factors $H'_{2}$ and $H''_{2}$.
Assign $1$ and $2$ to all edges of $H'_{2}$ and $H''_{2}$, respectively.
 By Lemma \ref{qr}, there exists a function $f: E(H_1)
\rightarrow \{2, 3, 4\}$ such that for every $u \in V(H_1)$,
$\sum_{v \in N_{H_1}(u)}f(uv)=8$. Now, assign $-2$ to  every edge in $E(G)\setminus E(H)$ and we are done.


Now, let $r\geq 9$ be an odd integer. By Theorem
\ref{kano},  for every $k$, $k \leq \frac{2r}{3}$, $G$ has a
$[k-1, k]$-factor whose components are regular. Let $k=\lfloor
\frac{2r}{3} \rfloor$,  $k'= r-k$, and  $H$ be a $[k-1,
k]$-factor of $G$ such that $H_1$ is the union of the $(k-1)$-regular
components  of $H$ and $H_2=H \setminus H_1$. It can be easily
checked that $k \leq 2k' \leq 2k-4$. Hence  by Lemma \ref{qr}, there
exists a function $f:E(H_1) \longrightarrow \{2, 3, 4\}$
such that for every $u \in V(H_1)$, $\sum_{v \in
N_{H_1}(u)}f(uv)= 4k'+4$. Also by Lemma \ref{qr}, there exists a
function $f:E(H_2) \longrightarrow \{2, 3, 4\}$  such that
for every $v \in V(H_2)$,
 $\sum_{v \in N_{H_2}(u)}f(uv)= 4k'$.
 Finally assign $-4$ to  every edge of $E(G)\setminus E(H)$. Now, by Theorem \ref{evenreg}   the proof is complete. }
\end{proof}

\noindent {\bf Acknowledgements.}  The 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
second author were in part supported by grants from IPM (No.
90050212) and (No.  88050042), respectively.



%\providecommand{\bysame}{\leavevmode\hbox
%to3em{\hrulefill}\thinspace}

\begin{thebibliography}{}{\small

%\begin{thebibliography}{10}

\bibitem{zerosum1} S. Akbari, G. B. Khosrovshahi, A. Mahmoody and N. Gharaghani, On zero-sum $6$-flows of graphs, Linear
Algebra and its Applications 430 (2009), 3047--3052.

\bibitem{d} S. Akbari, A. Daemi, O. Hatami, A. Javanmard and A. Mehrabian, Zero-sum flows in regular graphs,  Graphs Combin. 26 (2010), 603–-615.

\bibitem{bondy}
J.A. Bondy, U.S.R. Murty,  Graph Theory with Applications, North
Holland, New York, 1976.

\bibitem{bouchet} A. Bouchet, Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory, Ser. B 34 (1983),
279-292.

\bibitem{devos} M. DeVos, Flows in bidirected graphs, preprint.


\bibitem{kano}
M. Kano, Factors of regular graphs, J. Combin. Theory Ser. B 41
(1986), 27-36.

\bibitem{handbook}
J. Petersen, Die theorie der regul$\ddot{a}$ren graphs, Acta Math. (15) (1891), 193-220.

\bibitem{tut} W.T. Tutte, On the imbedding of linear graphs in surfaces,
Proc. London Math. Soc. Ser 2 51 (1949), 464–-483.



\bibitem{xui} R. Xu and C.Q. Zhang, On flows in bidirected graphs, Discrete Math. (2005), No. 299,
335-343.

\bibitem{zyk} O. Zyka,  Nowhere-zero $30$-flow on bidirected graphs, Charles University, Praha, 1987, KAM-DIMATIA Series
87-26.


}\end{thebibliography}{}


\end{document}
