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