Nowhere-zero flows in low genus graphs

A nowhere-zero k-flow is an assignment of edge directions and integer weights in the range 1,…, k ? 1 to the edges of an undirected graph such that at every vertex the flow in is equal to the flow out. Tutte has conjectured that every bridgeless graph has a nowhere-zero 5-flow. We show that a counterexample to this conjecture, minimal in the class of graphs embedded in a surface of fixed genus, has no face-boundary of length <7. Moreover, in order to prove or disprove Tutte's conjecture for graphs of fixed genus γ, one has to check graphs of order at most 28(γ ? 1) in the orientable case and 14(γ ? 2) in the nonorientable case. So, in particular, it follows immediately that every bridgeless graph of orientable genus ?1 or nonorientable genus ?2 has a nowhere-zero 5-flow. Using a computer, we checked that all graphs of orientable genus ?2 or nonorientable genus ?4 have a nowhere-zero 5-flow.     

Nowhere-zero 6-flows

We prove that every graph with no isthmus has a nowhere-zero 6-flow, that is, a circulation in which the value of the flow through each edge is one of ±1, ±2,…, ±5. This improves Jaeger's 8-flow theorem, and approaches Tutte's 5-flow conjecture.     

Flows in 3-edge-connected bidirected graphs

It was conjectured by A. Bouchet that every bidirected graph which admits a nowhere-zero k-flow admits a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. O. Zyka improved the result with 6 replaced by 30. R. Xu and C. Q. Zhang showed that the conjecture is true for 6-edge-connected graph, which is further improved by A. Raspaud and X. Zhu for 4-edge-connected graphs. The main result of this paper improves Zyka’s theorem by showing the existence of a nowhere-zero 25-flow for all 3-edge-connected graphs.     

Six-flows on almost balanced signed graphs

In 1983, Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow. By Seymour's 6-flow theorem, Bouchet's conjecture holds for signed graphs with all edges positive. Recently, Rollová et al proved that every flow-admissible signed cubic graph with two negative edges admits a nowhere-zero 7-flow, and admits a nowhere-zero 6-flow if its underlying graph either contains a bridge, or is 3-edge-colorable, or is critical. In this paper, we improve and extend these results, and confirm Bouchet's conjecture for signed graphs with frustration number at most two, where the frustration number of a signed graph is the smallest number of vertices whose deletion leaves a balanced signed graph.     

Tutte's 5-flow conjecture for graphs of nonorientable genus 5

We develop four constructions for nowhere-zero 5-flows of 3-regular graphs that satisfy special structural conditions. Using these constructions we show a minimal counter-example to Tutte's 5-Flow Conjecture is of order ≥44 and therefore every bridgeless graph of nonorientable genus ≤5 has a nowhere-zero 5-flow. One of the structural properties is formulated in terms of the structure of the multigraph G(F) obtained from a given 3-regular graph G by contracting the cycles of a 2-factor F in G. © 1996 John Wiley & Sons, Inc.     

On Group Connectivity of Graphs

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z ₃-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured that every 5-edge-connected graph is Z ₃-connected. These two conjectures are in general open and few results are known so far. A weaker version of Tutte’s conjecture states that every 4-edge-connected graph with each edge contained in a circuit of length at most 3 admits a nowhere-zero Z ₃-flow. Devos proposed a stronger version problem by asking if every such graph is Z ₃-connected. In this paper, we first answer this later question in negative and get an infinite family of such graphs which are not Z ₃-connected. Moreover, motivated by these graphs, we prove that every 6-edge-connected graph whose edge set is an edge disjoint union of circuits of length at most 3 is Z ₃-connected. It is a partial result to Jaeger’s Z ₃-connectivity conjecture. Received: May 23, 2006. Final version received: January 13, 2008     

Almost all 5-regular graphs have a 3-flow

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.     

Tutte’s 5-flow conjecture for highly cyclically connected cubic graphs

In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let ω(G) be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph G. Tutte’s conjecture is equivalent to its restriction to cubic graphs with ω≥2. We show that if a cubic graph G has no edge cut with fewer than edges that separates two odd cycles of a minimum 2-factor of G, then G has a nowhere-zero 5-flow. This implies that if a cubic graph G is cyclically n-edge connected and , then G has a nowhere-zero 5-flow.     

Restrictions On Smallest Counterexamples To The 5-Flow Conjecture

Using counting arguments, we show that every smallest counterexample to Tutte’s 5-flow Conjecture (that every bridgeless graph has a nowhere-zero 5-flow) has girth at least 9. * This work was supported by Science and Technology Assistance Agency under the contract No. APVT-51-027604 and partially by VEGA grant 2/4004/04. The author was also affiliated at the School of Mathematics, Georgia Institute of Technology, the Department of Mathematics, Vanderbilt University.     

Minimum cycle coverings and integer flows

It was conjectured by Fan that if a graph G = (V,E) has a nowhere-zero 3-flow, then G can be covered by two even subgraphs of total size at most |V| + |E| - 3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the Chinese postman problem and the solution of minimum cycle covering problem are equivalent for any graph admitting a nowhere-zero 4-flow.     

图的字典积的非零整数流(英文)

充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流.     

NASH EQUILIBRIUM OF TWO GAME MODELS ON THE RANDOM SOCIAL NETWORK

A graph $G$ is $k$-triangular if each of its edge is contained in at least $k$ triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1 T_2\cdots T_k$ in $G$ such that for $1\leq i\leq k-1, |E(T_i )\cap E(T_{i+1})|=1$ and $E(T_i)\cap E(T_j)=\emptyset$ if $j>i+1$. Two edges $e,e''\in E(G)$ are triangularly connected if there is a triangle-path $T_1,T_2,\cdots, T_k$ in $G$ such that $e\in E(T_1)$ and $e''\in E(T_k)$. Two edges $e,e''\in E(G)$ are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph $G$ is ${\mathbb Z}_3$-connected, unless it has a triangularly connected component which is not ${\mathbb Z}_3$-connected but admits a nowhere-zero 3-flow.     

Nowhere-zero 4-flow in almost Petersen-minor free graphs

Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let be the graph obtained from the Petersen graph by contracting μ edges from a perfect matching. In this paper we prove that every bridgeless -minor free graph admits a nowhere-zero 4-flow.     

Nowhere-zero 3-flow of graphs with small independence number

Tutte’s $3$-flow conjecture states that every $4$-edge-connected graph admits a nowhere-zero $3$-flow. In this paper, we characterize all graphs with independence number at most $4$ that admit a nowhere-zero $3$-flow. The characterization of $3$-flow verifies Tutte’s $3$-flow conjecture for graphs with independence number at most $4$ and with order at least $21$. In addition, we prove that every odd-$5$-edge-connected graph with independence number at most $3$ admits a nowhere-zero $3$-flow. To obtain these results, we introduce a new reduction method to handle odd wheels.     

The size of graphs without nowhere-zero 4-flows

Let G be a 2-edge-connected simple graph with order n. We show that if | V(G)| ≤ 17, then either G has a nowhere-zero 4-flow, or G is contractible to the Petersen graph. We also show that for n large, if | V(G)| n ? 17/2 + 34, then either G has a nonwhere-zero 4-flow, or G can be contracted to the Petersen graph. © 1995 John Wiley & Sons, Inc.     

Decomposition of the Flow Polynomial

The flow polynomials denote the number of nowhere-zero flows on graphs, and are related to the well-known Tutte polynomials and chromatic polynomials. We will show the decomposition of the flow polynomials by edge-cuts and vertex-cuts of size 2 or 3. Moreover by using this decomposition, we will consider what kind of graphs have the same flow polynomials. Another application of the decomposition results is that if a bridgeless graph G does not admit a nowhere-zero k-flow and G has a small vertex- or edge-cut, then a proper bridgeless subgraph of G (a graph minor) does not admit a nowhere-zero k-flow either.     

Nowhere-zero 15-flow in 3-edge-connected bidirected graphs

It was conjectured by Bouchet that every bidirected graph which admits a nowhere-zero κ flow will admit a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. Zyka improved the result with 6 replaced by 30. Xu and Zhang showed that the conjecture is true for 6-edge-connected graphs. And for 4-edge-connected graphs, Raspaud and Zhu proved it is true with 6 replaced by 4. In this paper, we show that Bouchet＇s conjecture is true with 6 replaced by 15 for 3-edge-connected graphs.     

Hypothetical complexity of the nowhere-zero 5-flow problem

We show that if the well-known 5-Flow Conjecture of Tutte is not true, then the problem to determine whether a (cubic) graph admits a nowhere-zero 5-flow is NP-complete. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 1–11, 1998     

Integer flows

A k-flow is an assignment of edge directions and integer weights in the range 1, …., k – 1 to the edges of an undirected graph so that ateach vertex the flow in is equal to the flow out. This paper gives a polynomial algorithm for finding a 6-flow that applies uniformly to each graph. The algorithm specializes to give a 5-flow for planar graphs.     

Cycle covers of graphs with a nowhere-zero 4-flow

It is shown that the edges of a simple graph with a nowhere-zero 4-flow can be covered with cycles such that the sum of the lengths of the cycles is at most |E(G)| + |V(G)| ?3. This solves a conjecture proposed by G. Fan.