\documentstyle[11pt, amsfonts]{article} %\documentstyle[11pt]{article} \newcommand{\hide}[1]{} %\newcommand{\R}{{\cal R}} %Use only if amsfonts are unavailable \newcommand{\R}{{\mathbb R}} \newcommand{\s}{\scriptscriptstyle} \newcommand{\deltaplus }{\delta^{\mbox{\raisebox{1pt}{$\s +$}}}\!} \newcommand{\deltaminus}{\delta^{\mbox{\raisebox{1pt}{$\s -$}}}\!} % Test: $\delta^+ X$, $\deltaplus X$, $\delta^- X$, $\deltaminus X$, %\newtheorem{lemma}{\sc Lemma}[section]% \newtheorem{lemma}{\sc Lemma}% Sectionless Paper \newtheorem{theorem}[lemma]{\sc Theorem}% \newtheorem{proposition}[lemma]{\sc Proposition}% \newtheorem{corollary}[lemma]{\sc Corollary}% \newtheorem{claim}[lemma]{\sc Claim}% \newtheorem{conjecture}[lemma]{\sc Conjecture}% \newtheorem{remark}[lemma]{\sc Remark}% \newtheorem{note}[lemma]{\sc Note}% \newtheorem{algorithm}[lemma]{\sc Algorithm}% \newtheorem{example}[lemma]{\sc Example}% \newtheorem{observation}[lemma]{\sc Observation}% \newtheorem{definition}[lemma]{\sc Definition}{}% \newtheorem{question}[lemma]{\sc Question}{}% \newtheorem{numbered}[lemma]{\sc}% %%%%%% Choose end-of-proof symbol %\newcommand{\QED}{Q.E.D.} % Q.E.D. %\newcommand{\QED}{$Box$} % Hollow box %\newcommand{\QED}{\raisebox{2pt}{\framebox[7pt]{}}} % Another hollow box \newcommand{\QED}{{\rule[0pt]{6pt}{6pt}}} % Solid Box \newenvironment{proof}{\noindent{\sc Proof:}} {\hfill \QED \\} \newenvironment{proofT}{\noindent{\sc Proof of Theorem \ref{main}.}}{\hfill \QED\\} \newenvironment{sketch}{\noindent{\sc Sketch of proof.}} {\hfill \QED \\} %\voffset=-1in \setlength{\itemsep}{6pt} %\topsep=0in %\partopsep=0in \setlength{\evensidemargin}{.22truein} \setlength{\oddsidemargin}{.22truein} \setlength{\textwidth}{6.6truein} \setlength{\topmargin}{0.25truein} \setlength{\textheight}{8.8truein} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \setlength{\parindent}{1pc} \setlength{\hoffset}{-0.4truein} \title{{The circular flow number of a 6-edge connected graph is less than four}} \author{ Anna Galluccio\thanks {Supported by NATO-CNR Fellowship; this work was done while the author was visiting the Dept. of Mathematics and Statistics at Simon Fraser University, Canada;}\\ {\normalsize Istituto di Analisi dei Sistemi ed}\\ {\normalsize Informatica - CNR}\\ {\normalsize Roma, Italy}\\ {\normalsize galluccio@iasi.rm.cnr.it}\\ \and Luis A. Goddyn\thanks {Supported by a National Sciences and Engineering Research Council Research Grant} \\ {\normalsize Department of Mathematics and Statistics}\\ {\normalsize Simon Fraser University}\\ {\normalsize Burnaby, B.C., Canada}\\ {\normalsize goddyn@math.sfu.ca}\\ } %\date{\today} \date{} \begin{document} \maketitle \begin{abstract} We show that every $6$-edge connected graph admits a circulation whose range lies in the interval~$[1,3)$. \vspace{2ex} \noindent {\sc Keywords:} {\it nowhere zero flow, circular flow number, star flow number, circulation, eulerian graph, cogirth even, $T$-join.} \end{abstract} \vspace{1ex} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \section{Introduction} The {\it circular flow number\/} $\phi_c(G)$ of a (finite) graph $G$ is defined by $$ \phi_c(G) = \inf\{r \in \R : \mbox{ some orientation $\vec{G}$ admits a circulation } f: E(\vec{G}) \rightarrow [1,r-1] \}. $$ This parameter is a refinement of the well studied {\it flow number\/} % $\phi(G)$ $\phi(G) := \lceil \phi_c(G)\rceil$, which was introduced by Tutte as a dual to the chromatic number. Since $\phi_c(G) \ge 2$ with equality if and only if $G$ is eulerian, the circular flow number may be regarded as a measure of how close a graph is to being eulerian. % % %The flow number $\phi(G)$ of a (finite) graph $G$ is a well studied invariant %which was introduced by Tutte as a parameter dual to the chromatic number. %The circular flow number $\phi_c(G)$ is a refinement %of the flow number in that $\phi(G) = \lceil \phi_c(G)\rceil$ for %all graphs $G$. %Since $\phi_c(G) \ge 2$ with equality if and only if $G$ is eulerian, %the circular flow number may be regarded as a measure of how close %a graph is to being eulerian. % % %The following list summarizes some of the major results and conjectures %regarding flow number and edge connectivity. %These and other results can be found in \cite{Sey-HoC}. The following results and conjectures can be found in \cite{Sey-HoC}. \begin{description} \item[\hspace{1em}-] {\sc Theorem }(Seymour, 1979) Every $2$-edge connected graph $G$ has $\phi_c(G) \le 6$. \item[\hspace{1em}-] {\sc Conjecture }(Tutte, 1954) Every $2$-edge connected graph $G$ has $\phi_c(G) \le 5$. \item[\hspace{1em}-] {\sc Theorem }(Jaeger, 1975) Every $4$-edge connected graph $G$ has $\phi_c(G) \le 4$. \item[\hspace{1em}-] {\sc Conjecture }(Tutte, 1966) Every $4$-edge connected graph $G$ has $\phi_c(G) \le 3$. \end{description} This list suggests that the circular flow number might decrease as edge connectivity increases. For this and other reasons, the following has been asked \cite{GGH}. \begin{question} Is it true that \ $\sup \{ \phi_c(G) : \mbox{\rm $G$ is $k$-edge connected}\}\!\rightarrow 2$ as $k \rightarrow \infty$? \end{question} The answer is ``yes'' for graphs of bounded genus \cite{Zhang}, but little progress has been made for general graphs. In this note we present a refinement of Jaeger's result. \begin{theorem}\label{main} Every $6$-edge connected graph $G$ has $\phi_c(G)< 4$. \end{theorem} It suits our purpose to use the following ``Minty-like'' formula for $\phi_c$ which arises directly from Hoffman's circulation condition (see \cite{GTZ}). If $G=(V,E)$ is finite and 2-edge connected, then \begin{equation}\label{phi-def} \phi_c(G)=\min_{\vec G} \max _{\emptyset\, \ne X \subset V} \frac {|\delta X|}{|\deltaplus X |} \end{equation} where $\vec G$ ranges over the strong orientations of $G$. (Here $\deltaplus X$ denotes the set of arcs from $X$ to $V-X$, and $\delta X = \deltaplus X \cup \deltaplus (V-X) $.) % (Here $\deltaplus X $ ($\deltaminus X $) denotes % the set of arcs leaving (entering) $X$, % and $\delta X = \deltaplus X \cup \deltaminus X $.) % \section{The proof} %Let $G$ be a graph. %Where no confusion arises, we identify a subgraph of $G$ with its edge set. Let $T \subseteq V(G)$. A {\it $T$-join\/} in $G$ is a subset $J \subseteq E(G)$ such that $T$ is the set of odd-degree vertices in the induced subgraph $G[J]$. An $\emptyset$-join is usually called a {\it cycle\/} or {\it even subgraph\/} of $G$. % We use two standard results regarding trees and $T$-joins. The first is folklore, and the second was first proved by Nash-Williams \cite{NW}. % \begin{lemma}\label{tree-join} Any tree $H$ contains a $T$-join, for any $T \subseteq V(H)$ of even cardinality. \end{lemma} % \begin{lemma}\label{connect-tree} Any $2k$-edge connected graph contains $k$ edge-disjoint spanning trees. \end{lemma} % \begin{lemma} \label{T1T2} Let $H_1$ and $H_2$ be edge-disjoint spanning trees of a graph $G$ and let $T$ be an even subset of $V(G)$. Then $H_1\cup H_2$ contains a $T$-join which is spanning and connected. \end{lemma} % \begin{proof} Let $V_1$ be the set of odd-degree vertices in $H_1$. The symmetric difference $V_1 \Delta T$ has even cardinality so by Lemma \ref{tree-join}, $H_2$ contains a $(V_1 \Delta T)$-join $J_2$. Let $F = H_1 \cup J_2$. Since $H_1$ and $J_2$ are edge disjoint, $F$ is a $T$-join. Furthermore $E(H_1) \subseteq F$ so $F$ spans $G$ and is connected. \end{proof} \begin{lemma} \label{linprog} Consider the polyhedron %$ P = \{ x=[x_1\;x_2\;\ldots\; x_8]^T : Ax = b,\: x \ge 0 \} $ $ P = \{ x \in \R^8 : Ax = b,\: x \ge 0 \} $ where $$ %[A | b] = \left[\begin{array}{*{8}{r}|r} [A | b] = \left[\begin{array}{*{8}{@{\hspace{0.5em}}r}|r} 1& 1& 1& 0& -1& -1& -1& 0\;& 0 \\ 1& 0& -1& 1& -1& 0& 1& -1\;& 0 \\ 1&\;\;1&\;\;1&\;\;1&\;\;\;\;1&\;\;1&\;\;1&\;\;1\;&\;1 \end{array}\right]. $$ Then the linear program $z^* = \min \{ [1\;1\;1\;1\;0\;0\;0\;0] x : x \in P \}$ has a unique optimum solution $x^* = \left[\frac14\;0\;0\;0\;0\;0\;\frac14 \;\frac12\right]^T$ with value $z^* = \frac14$. \end{lemma} \begin{proof} It is routine to check that $x^*$ is $P$-feasible and that the vector $ y^* = \left[\frac12\;\frac14\;\frac14\right]$ is a feasible solution to the dual linear program $\max \{ y[0\;0\;1]^T : yA \le [1\;1\;1\;1\;0\;0\;0\;0] \}$. Both objective values equal $\frac14$ so $(x^*,y^*)$ is an optimal dual pair. To show uniqueness we demonstrate that the primal objective vector is in the strict interior of a full dimensional cone generated by normals of active (tight) constraints at $x^*$. Writing $x = [x_1\;x_2\;\ldots\; x_8]^T$, the active constraints are the three equations $Ax = b$ and the five equations $x_i=0$, $i=2,3,4,5,6$. Indeed we have the positive linear combination $$ [1\;1\;1\;1\;0\;0\;0\;0] = \left[\frac12\;\,\frac14\;\,\frac14\right]\!A + \frac14e_2 + \frac12e_3 + \frac12e_4 + \frac12e_5 + \frac14e_6 $$ where $e_i$ is the $i$-th standard unit vector in $\R^8$. The cone is full dimensional since the first, seventh and eighth columns of $A$ are linearly independent. \end{proof} \begin{proofT} Let $V_1$ be the vertices of odd degree in $G$. By Lemma \ref{connect-tree}, $G$ has three edge disjoint spanning trees. So by Lemmas \ref{tree-join} and \ref{T1T2}, $G$ has two edge-disjoint $V_1$-joins, $J_1$, $J_2$, such that $J_2$ spans $G$ and is connected. % Let $\vec {C_1}$ and $\vec{C_2}$ be eulerian orientations of the complementary cycles $C_1=E-J_1$ and $C_2=E-J_2$. Note that % $J_1=C_2-C_1$, $J_2=C_1-C_2$ and $C_1 \cup C_2 = E(G)$. % Let $\vec{G}$ be the {\it lexicographic orientation\/} of $G$ induced by $(\vec{C_1}, \vec{C_2})$. That is, we orient each edge $e \in E(G) \cap C_1$ as it is oriented in $\vec{C_1}$, and we orient each $e \in E(G) - C_1$ as it is oriented in $\vec{C_2}$. Let $X$ be a proper nonempty subset of $V(\vec{G})$. We shall show that $\frac {|\deltaplus X |}{|\delta X |} > \frac14$ and the result follows from (\ref{phi-def}). We associate with every edge $e \in \delta X $ an ordered pair $\sigma\tau \in \{+,-,0\}^2$ where $$ \sigma = \left\{ \begin{tabular}{ll} $+$ & \mbox{if $\vec{C_1}$ traverses $e$ from $X$ to $V-X$} \\ $-$ & \mbox{if $\vec{C_1}$ traverses $e$ from $V-X$ to $X$} \\ $0$ & \mbox{if $e \not\in C_1$} \end{tabular} \right. $$ and where $\tau$ is defined similarly using $C_2$ in place of $C_1$. The pair $\sigma\tau$ is called the {\it type\/} of $e$. Let $x_{\sigma\tau}$ denote the proportion of edges in $\delta X $ having type $\sigma\tau$. Since $C_1 \cup C_2 = E(G)$, no edge has type $00$. We consider the $8$-dimensional column vector $$ x = [x_{\s ++}\;x_{\s +0}\;x_{\s +-}\;x_{\s 0+}\; x_{\s --}\;x_{\s -0}\;x_{\s -+}\;x_{\s 0-}]^T. $$ Since each $\vec{C_i}$ traverses $\delta X $ the same number of times in each direction, $x$ is a feasible point in the polyhedron $P$ of Lemma \ref{linprog}. % Because $\vec{G}$ is defined lexicographically, we have $$ \frac {|\deltaplus X |}{|\delta X |} = [1\;1\;1\;1\;0\;0\;0\;0] x$$ so this ratio is bounded below by the optimum value of the linear program of Lemma \ref{linprog}. By that lemma, the unique optimum solution is $ x^* = \left[\frac14\;0\;0\;0\;0\;0\;\frac14\;\frac12\right]^T $ with value $z^* = \frac14$. Since $J_2$ is spanning and connected, we have $\delta X - C_2 \ne \emptyset$, so $\,x_{\s +0} + \, x_{\s -0} > 0$. Thus $x \ne x^*$ and $[1\;1\;1\;1\;0\;0\;0\;0] x > \frac14$ as claimed. \end{proofT} \noindent {\sc Remark: }We have not proved that $ \sup\{\phi_c(G) : G \mbox{ is $k$-edge connected }\} < 4 $ for any value of $k$. To do so by our method would require finding disjoint $V_1$-joins $J_1$, $J_2$ such that $|J_1 \cap \delta X | \ge c |\delta X |$ for all $X \subseteq V$ and some $c>0$. Using only Lemmas \ref{tree-join} and \ref{connect-tree}, the best we can ensure is $|J_1 \cap \delta X | \ge \lfloor\frac{k-4}{2}\rfloor$. \bigskip \bibliographystyle{siam} %\bibliographystyle{kluwer} \bibliography{Flowbib} \end{document}