The circular flow number of a 6-edge connected graph is less than four

Anna Galluccio^{∗}

Istituto di Analisi dei Sistemi ed Informatica - CNR Roma, Italy galluccio@iasi.rm.cnr.it

Luis A. Goddyn^{†}

Department of Mathematics and Statistics Simon Fraser University Burnaby, B.C., Canada goddyn@math.sfu.ca

Abstract We show that every 6-edge connected graph admits a circulation whose range lies in the

interval [1, 3).

Keywords: nowhere zero flow, circular flow number, star flow number, circulation, eulerian graph, cogirth even, T -join.

The circular flow number ϕ_{c}(G) of a (finite) graph G is defined by

ϕ_{c}(G) = inf{r ∈ ℝ : some orientation G⃗ admits a circulation f : E(G⃗) → [1, r − 1]}.

This parameter is a refinement of the well studied flow number ϕ(G) := ⌈ϕ_{c}(G)⌉, which was introduced by Tutte as a dual to the chromatic number. Since ϕ_{c}(G) ≥ 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 results and conjectures can be found in [4].

- Theorem (Seymour, 1979) Every 2-edge connected graph G has ϕ_{c}(G) ≤ 6.

- Conjecture (Tutte, 1954) Every 2-edge connected graph G has ϕ_{c}(G) ≤ 5.

- Theorem (Jaeger, 1975) Every 4-edge connected graph G has ϕ_{c}(G) ≤ 4.

- Conjecture (Tutte, 1966) Every 4-edge connected graph G has ϕ_{c}(G) ≤ 3.

This list suggests that the circular flow number might decrease as edge connectivity increases. For this and other reasons, the following has been asked [1].

Question 1 Is it true that sup{ϕ_{c}(G) : G is k-edge connected}→ 2 as k → ∞?

The answer is “yes” for graphs of bounded genus [5], but little progress has been made for general graphs. In this note we present a refinement of Jaeger’s result.

Theorem 2 Every 6-edge connected graph G has ϕ_{c}(G) < 4.

∗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;

†Supported by a National Sciences and Engineering Research Council Research Grant

It suits our purpose to use the following “Minty-like” formula for ϕ_{c} which arises directly from Hoffman’s circulation condition (see [2]). If G = (V, E) is finite and 2-edge connected, then

ϕ_{c}(G) = min_{G⃗} max_{∅ ≠X⊂V} \frac{|δX|}{|δ^{+}X|}  (1)

where G⃗ ranges over the strong orientations of G. (Here δ^{+}X denotes the set of arcs from X to V − X, and δX = δ^{+}X ∪ δ^{+}(V − X).)

Let T ⊆ V (G). A T -join in G is a subset J ⊆ E(G) such that T is the set of odd-degree vertices in the induced subgraph G[J]. An ∅-join is usually called a cycle or 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 [3].

Lemma 3 Any tree H contains a T -join, for any T ⊆ V (H) of even cardinality.

Lemma 4 Any 2k-edge connected graph contains k edge-disjoint spanning trees.

Lemma 5 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} ∪ H_{2} contains a T -join which is spanning and connected.

Proof: Let V_{1} be the set of odd-degree vertices in H_{1}. The symmetric difference V_{1}ΔT has even cardinality so by Lemma 3, H_{2} contains a (V_{1}ΔT)-join J_{2}. Let F = H_{1} ∪ J_{2}. Since H_{1} and J_{2} are edge disjoint, F is a T -join. Furthermore E(H_{1}) ⊆ F so F spans G and is connected.

Lemma 6 Consider the polyhedron P = {x ∈ ℝ^{8} : Ax = b, x ≥ 0} where

[A|b] = [ \begin{matrix}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{matrix} ] .

Then the linear program z^{∗} = min{[1 1 1 1 0 0 0 0]x : x ∈ P } has a unique optimum solution x^{∗} = [\frac{1}{4} 0 0 0 0 0 \frac{1}{4} \frac{1}{2}]^{T} with value z^{∗} = \frac{1}{4}.

Proof: It is routine to check that x^{∗} is P -feasible and that the vector y^{∗} = [\frac{1}{2} \frac{1}{4} \frac{1}{4}] is a feasible solution to the dual linear program max{y[0 0 1]^{T} : yA ≤ [1 1 1 1 0 0 0 0]}. Both objective values equal \frac{1}{4} 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} … 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] = [\frac{1}{2} \frac{1}{4} \frac{1}{4}]A + \frac{1}{4}e_{2} + \frac{1}{2}e_{3} + \frac{1}{2}e_{4} + \frac{1}{2}e_{5} + \frac{1}{4}e_{6}

where e_{i} is the i-th standard unit vector in ℝ^{8}. The cone is full dimensional since the first, seventh and eighth columns of A are linearly independent.

Proof of Theorem 2. Let V_{1} be the vertices of odd degree in G. By Lemma 4, G has three edge disjoint spanning trees. So by Lemmas 3 and 5, G has two edge-disjoint V_{1}-joins, J_{1}, J_{2}, such that J_{2} spans G and is connected. Let C⃗_{1} and C⃗_{2} be eulerian orientations of the complementary cycles C_{1} = E − J_{1} and C_{2} = E − J_{2}. Note that C_{1} ∪ C_{2} = E(G). Let G⃗ be the lexicographic orientation of G induced by (C⃗_{1}, C⃗_{2}). That is, we orient each edge e ∈ E(G) ∩ C_{1} as it is oriented in C⃗_{1}, and we orient each e ∈ E(G) − C_{1} as it is oriented in C⃗_{2}.

Let X be a proper nonempty subset of V (G⃗). We shall show that \frac{|δ^{+}X|}{|δX|} > \frac{1}{4} and the result follows from (1). We associate with every edge e ∈ δX an ordered pair στ ∈ {+, −, 0}^{2} where

σ = \{ \begin{matrix}+ & if C⃗_{1} traverses e from X to V − X \\ − & if C⃗_{1} traverses e from V − X to X \\ 0 & if e ∉ C_{1} \end{matrix}

and where τ is defined similarly using C_{2} in place of C_{1}. The pair στ is called the type of e.

Let x_{στ} denote the proportion of edges in δX having type στ. Since C_{1} ∪ C_{2} = E(G), no edge has type 00. We consider the 8-dimensional column vector

x = [x_{++} x_{+0} x_{+−} x_{0+} x_{−−} x_{−0} x_{−+} x_{0−}]^{T} .

Since each C⃗_{i} traverses δX the same number of times in each direction, x is a feasible point in the polyhedron P of Lemma 6. Because G⃗ is defined lexicographically, we have

\frac{|δ^{+}X|}{|δ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 6. By that lemma, the unique optimum solution is x^{∗} = [\frac{1}{4} 0 0 0 0 0 \frac{1}{4} \frac{1}{2}]^{T} with value z^{∗} = \frac{1}{4}. Since J_{2} is spanning and connected, we have δX − C_{2} ≠ ∅, so x_{+0} + x_{−0} > 0. Thus x ≠ x^{∗} and [1 1 1 1 0 0 0 0]x > \frac{1}{4} as claimed.

Remark: We have not proved that sup{ϕ_{c}(G) : G 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} ∩ δX| ≥ c|δX| for all X ⊆ V and some c > 0. Using only Lemmas 3 and 4, the best we can ensure is |J_{1} ∩ δX| ≥ ⌊\frac{k−4}{2}⌋.

References

[1] A. Galluccio, L. A. Goddyn, and P. Hell, High girth graphs avoiding a minor are nearlybipartite, (1999).

[2] L. A. Goddyn, M. Tarsi, and C.-Q. Zhang, On (k, d)-colorings and fractional nowhere zero flows, J. Graph Theory, 28 (1998), pp. 155–161.

[3] C. S. J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc., 36 (1961), pp. 445–450.

[4] P. D. Seymour, Nowhere-zero flows, in Handbook of Combinatorics, R. Graham, M. Grötschel, and L. Lovász, eds., vol. 1, Elsevier, Amsterdam, 1995. Appendix to chapter 4.

[5] C. Q. Zhang, Circular flows of nearly eulerian graphs and vertex-splitting, (1999). Preprint.