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.     

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     

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.     

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.     

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.     

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

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

Tutte's 5-flow conjecture for the projective plane

Heawood proved that every planar graph with no 1-cycles is vertex 5-colorable, which is equivalent to the statement that every planar graph with no 1-bonds has a nowhere-zero 5-flow. Tutte has conjectured that every graph with no 1-bonds has a nowhere-zero 5-flow. We show that Tutte's 5-Flow Conjecture is true for all graphs embeddable in the real projective plane.     

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.     

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.     

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.     

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.     

Nowhere-zero 3-flows and modulo k-orientations

The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutte?s 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is _Z3$Z_3$-connected, Jaeger?s circular flow conjecture (1984) that for every odd natural number k?3$k?3$, every (2k−2)$(2k-2)$-edge-connected graph has a modulo k  -orientation, etc. It was proved recently by Thomassen that, for every odd number k?3$k?3$, every (2k²+k)$(2k^2+k)$-edge-connected graph G has a modulo k-orientation; and every 8-edge-connected graph G   is _Z3$Z_3$-connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassen?s method is refined to prove the following: For every odd number  k?3$k?3$, every  (3k−3)$(3k-3)$-edge-connected graph has a modulo k-orientation. As a special case of the main result, every 6-edge-connected graph is  _Z3$Z_3$-connected and admits therefore a nowhere-zero 3-flow. Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs.     

Flows, flow-pair covers and cycle double covers

In this paper, some earlier results by Fleischner [H. Fleischner, Bipartizing matchings and Sabidussi’s compatibility conjecture, Discrete Math. 244 (2002) 77-82] about edge-disjoint bipartizing matchings of a cubic graph with a dominating circuit are generalized for graphs without the assumption of the existence of a dominating circuit and 3-regularity. A pair of integer flows (D,f₁) and (D,f₂) is an (h,k)-flow parity-pair-cover of G if the union of their supports covers the entire graph; f₁ is an h-flow and f₂ is a k-flow, and . Then G admits a nowhere-zero 6-flow if and only if G admits a (4,3)-flow parity-pair-cover; and G admits a nowhere-zero 5-flow if G admits a (3,3)-flow parity-pair-cover. A pair of integer flows (D,f₁) and (D,f₂) is an (h,k)-flow even-disjoint-pair-cover of G if the union of their supports covers the entire graph, f₁ is an h-flow and f₂ is a k-flow, and for each {i,j}={1,2}. Then G has a 5-cycle double cover if G admits a (4,4)-flow even-disjoint-pair-cover; and G admits a (3,3)-flow parity-pair-cover if G has an orientable 5-cycle double cover.     

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.     

Smallest (1, 2)-eulerian weight and shortest cycle covering

The concept of a (1, 2)-eulerian weight was introduced and studied in several papers recently by Seymour, Alspach, Goddyn, and Zhang. In this paper, we proved that if G is a 2-connected simple graph of order n (n ≧ 7) and w is a smallest (1, 2)-eulerian weight of graph G, then |E_w=even | n - 4, except for a family of graphs. Consequently, if G admits a nowhere-zero 4-flow and is of order at least 7, except for a family of graphs, the total length of a shortest cycle covering is at most | V(G) | + |E(G) |- 4. This result generalizes some previous results due to Bermond, Jackson, Jaeger, and Zhang.     

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.     

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.     

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.     

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.     

Cayley Snarks and Almost Simple Groups

A Cayley snark is a cubic Cayley graph which is not 3-edge-colourable. In the paper we discuss the problem of the existence of Cayley snarks. This problem is closely related to the problem of the existence of non-hamiltonian Cayley graphs and to the question whether every Cayley graph admits a nowhere-zero 4-flow. So far, no Cayley snarks have been found. On the other hand, we prove that the smallest example of a Cayley snark, if it exists, comes either from a non-abelian simple group or from a group which has a single non-trivial proper normal subgroup. The subgroup must have index two and must be either non-abelian simple or the direct product of two isomorphic non-abelian simple groups. Received January 18, 2000 Research partially supported by VEGA grant 1/3213/96 Research partially supported by VEGA grants 1/3213/96 and 1/4318/97