Nowhere‐zero 3‐flows in products of graphs

A graph G is an odd‐circuit tree if every block of G is an odd length circuit. It is proved in this paper that the product of every pair of graphs G and H admits a nowhere‐zero 3‐flow unless G is an odd‐circuit tree and H has a bridge. This theorem is a partial result to the Tutte's 3‐flow conjecture and generalizes a result by Imrich and Skrekovski [7] that the product of two bipartite graphs admits a nowhere‐zero 3‐flow. A byproduct of this theorem is that every bridgeless Cayley graph G = Cay(Γ,S) on an abelian group Γ with a minimal generating set S admits a nowhere‐zero 3‐flow except for odd prisms. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Nowhere‐Zero 5‐Flows On Cubic Graphs with Oddness 4

Tutte's 5‐flow conjecture from 1954 states that every bridgeless graph has a nowhere‐zero 5‐flow. It suffices to prove the conjecture for cyclically 6‐edge‐connected cubic graphs. We prove that every cyclically 6‐edge‐connected cubic graph with oddness at most 4 has a nowhere‐zero 5‐flow. This implies that every minimum counterexample to the 5‐flow conjecture has oddness at least 6.     

A theorem on integer flows on cartesian products of graphs

It is shown that the Cartesian product of two nontrivial connected graphs admits a nowhere‐zero 4‐flow. If both factors are bipartite, then the product admits a nowhere‐zero 3‐flow. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 93–98, 2003     

Nowhere zero flows in line graphs

Cai an Corneil (Discrete Math. 102 (1992) 103–106), proved that if a graph has a cycle double cover, then its line graph also has a cycle double cover, and that the validity of the cycle double cover conjecture on line graphs would imply the truth of the conjecture in general. In this note we investigate the conditions under which a graph G has a nowhere zero k-flow would imply that L(G), the line graph of G, also has a nowhere zero k-flow. The validity of Tutte's flow conjectures on line graphs would also imply the truth of these conjectures in general.     

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.     

Circuit Covers of Signed Graphs

We introduce the concept of a signed circuit cover of a signed graph. A signed circuit cover is a natural analog of a circuit cover of a graph and is equivalent to a covering of the corresponding signed graphic matroid with circuits. As in the case of graphs, a signed graph has a signed circuit cover only when it admits a nowhere‐zero integer flow. In the present article, we establish the existence of a universal coefficient such that every signed graph G that admits a nowhere‐zero integer flow has a signed circuit cover of total length at most . We show that if G is bridgeless, then , and in the general case .     

Nowhere zero 4‐flow in regular matroids

Jensen and Toft 8 conjectured that every 2‐edge‐connected graph without a K₅‐minor has a nowhere zero 4‐flow. Walton and Welsh 19 proved that if a coloopless regular matroid M does not have a minor in {M(K_3,3), M*(K₅)}, then M admits a nowhere zero 4‐flow. In this note, we prove that if a coloopless regular matroid M does not have a minor in {M(K₅), M*(K₅)}, then M admits a nowhere zero 4‐flow. Our result implies the Jensen and Toft conjecture. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Strongly Regular Decompositions of the Complete Graph

We study several questions about amorphic association schemes and other strongly regular decompositions of the complete graph. We investigate how two commuting edge-disjoint strongly regular graphs interact. We show that any decomposition of the complete graph into three strongly regular graphs must be an amorphic association scheme. Likewise we show that any decomposition of the complete graph into strongly regular graphs of (negative) Latin square type is an amorphic association scheme. We study strongly regular decompositions of the complete graph consisting of four graphs, and find a primitive counterexample to A.V. Ivanov's conjecture which states that any association scheme consisting of strongly regular graphs only must be amorphic.     

Flows and Bisections in Cubic Graphs

A k‐weak bisection of a cubic graph G is a partition of the vertex‐set of G into two parts V₁ and V₂ of equal size, such that each connected component of the subgraph of G induced by () is a tree of at most vertices. This notion can be viewed as a relaxed version of nowhere‐zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere‐zero r‐flow has a ‐weak bisection. In this article, we study problems related to the existence of k‐weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4‐weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5‐weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5‐flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.     

Nowhere‐zero flows in tensor product of graphs

In this paper, we characterize graphs whose tensor product admit nowhere‐zero 3‐flow. The main result is: For two graphs G₁ and G₂ with δ ≥ 2 and G₂ not belonging to a well‐characterized class of graphs, the tensor product of G₁ and G₂ admits a nowhere‐zero 3‐flow. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 284–292, 2007     

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.     

一类完全多部图的色可选择性

如果一个图G的选择数等于它的色数,则称该图G是色可选择的．在2002年, Ohba给出如下猜想:每一个顶点个数小于等于2X(G) 1的图G是色可选择的．容易发现Ohba猜想成立的条件是当且仅当它对完全多部图成立,但是目前只是就某些特殊的完全多部图的图类证明了Ohba猜想的正确性．在本文我们证明图K6,3,2*(k-6),1*4(k≥6)是色可选择的,从而对图K6,3,2*(k-6),1*4(k≥6)和它们的所有完全k-部子图证明了Ohba猜想成立．     

Enumeration of weak isomorphism classes of signed graphs

A signed graph is a graph in which each line has a plus or minus sign. Two signed graphs are said to be weakly isomorphic if their underlying graphs are isomorphic through a mapping under which signs of cycles are preserved, the sign of a cycle being the product of the signs of its lines. Some enumeration problems implied by such a definition, including the problem of self-dual configurations, are solved here for complete signed graphs by methods of linear algebra over the two-element field. It is also shown that weak isomorphism classes of complete signed graphs are equal in number to other configurations: unlabeled even graphs, two-graphs and switching classes.     

Short cycle covers of graphs and nowhere‐zero flows

A shortest cycle cover of a graph G is a family of cycles which together cover all the edges of G and the sum of their lengths is minimum. In this article we present upper bounds to the length of shortest cycle covers, associated with the existence of two types of nowhere‐zero flows—circular flows and Fano flows. Fano flows, or Fano colorings, are nowhere‐zero ?‐flows on cubic graphs, with certain restrictions on the flow values meeting at a vertex. Such flows are conjectured to exist on every bridgless cubic graph. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 68:340‐348, 2011     

On the 4-color theorem for signed graphs

Máčajová et al. (2016) defined the chromatic number of a signed graph which coincides for all-positive signed graphs with the chromatic number of unsigned graphs. They conjectured that in this setting, for signed planar graphs four colors are always enough, generalizing thereby The Four Color Theorem. We disprove the conjecture.     

Shorter signed circuit covers of graphs

A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered by signed circuits of total length at most , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs.     

Zero‐sum flows in designs

Let D be a t ‐ ( v, k , λ) design and let N _i (D) , for 1 ≤ i ≤ t , be the higher incidence matrix of D , a ( 0 , 1 )‐matrix of size , where b is the number of blocks of D . A zero‐sum flow of D is a nowhere‐zero real vector in the null space of N ₁ ( D ). A zero‐sum k‐flow of D is a zero‐sum flow with values in { 1 , …, ±( k ? 1 )}. In this article, we show that every non‐symmetric design admits an integral zero‐sum flow, and consequently we conjecture that every non‐symmetric design admits a zero‐sum 5‐flow. Similarly, the definition of zero‐sum flow can be extended to N _i ( D ), 1 ≤ i ≤ t . Let be the complete design. We conjecture that N _t ( D ) admits a zero‐sum 3‐flow and prove this conjecture for t = 2 . © 2011 Wiley Periodicals, Inc. J Combin Designs 19:355‐364, 2011     

Bernstein-type Theorems in a Riemannian Manifold with an Irrotational Killing Vector Field

Mediterranean Journal of Mathematics - The minimal hypersurface equation for a graph in a Riemannian manifold which admits a nowhere zero Killing vector field, whose orthogonal distribution is...     

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.