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.     

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.     

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.     

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 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.     

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.     

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.     

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.     

Ergodic flows of positive entropy can be time changed to becomeK-flows

It is shown that every Kakutani equivalence class of ergodic measure preserving transformations of positive entropy containsK-automorphisms. Also, every ergodic flow of positive entropy can be time changed to become aK-flow and every ergodic automorphism of positive entropy is a cross-section of someK-flow.     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.     

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.     

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     

Nowhere-Zero 4-Flows,Simultaneous Edge-Colorings,And Critical Partial Latin Squares

It is proved in this paper that every bipartite graphic sequence with the minimum degree 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares.* Partially supported by RGC grant HKU7054/03P. Partially supported by the National Security Agency under Grants MDA904-00-1-00614 and MDA904-01-1-0022.     

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.     

Snarks and Flow-Critical Graphs

It is well-known that a 2-edge-connected cubic graph has a 3-edge-colouring if and only if it has a 4-flow. Snarks are usually regarded to be, in some sense, the minimal cubic graphs without a 3-edge-colouring. We defined the notion of 4-flow-critical graphs as an alternative concept towards minimal graphs. It turns out that every snark has a 4-flow-critical snark as a minor. We verify, surprisingly, that less than 5% of the snarks with up to 28 vertices are 4-flow-critical. On the other hand, there are infinitely many 4-flow-critical snarks, as every flower-snark is 4-flow-critical. These observations give some insight into a new research approach regarding Tutteʼs Flow Conjectures.     

Hechler’s theorem for the null ideal

We prove the following theorem: For a partially ordered set Q such that every countable subset of Q has a strict upper bound, there is a forcing notion satisfying the countable chain condition such that, in the forcing extension, there is a basis of the null ideal of the real line which is order-isomorphic to Q with respect to set-inclusion. This is a variation of Hechlers classical result in the theory of forcing. The corresponding theorem for the meager ideal was established by Bartoszyski and Kada.Research supported by NSERC. The first author thanks F.D. Tall and the Department of Mathematics at the University of Toronto for their hospitality during the academic year 2003/2004 when the present paper was completed.The second author was supported by Grant-in-Aid for Young Scientists (B) 14740058, MEXT.Mathematics Subject Classification (2000): 03E35, 03E17Revised version: 16 February 2004     

Zero-Sum Flows in Regular Graphs

For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)²-flow. Finally, the existence of k-flows for small graphs is investigated.     

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.     

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.     

On singularity of energy measures on self-similar sets

We provide general criteria for energy measures of regular Dirichlet forms on self-similar sets to be singular to Bernoulli type measures. In particular, every energy measure is proved to be singular to the Hausdorff measure for canonical Dirichlet forms on 2-dimensional Sierpinski carpets.Partially supported by Ministry of Education, Culture, Sports, Science and Technology, Grant-in-Aid for Encouragement of Young Scientists, 15740089.Mathematics Subject Classification (2000): 28A80 (60G30, 31C25, 60J60)