Reconfiguration of Nowhere-zero Flows
Daniel W. Cranston, Jiaao Li † , Bo Su † , Zhouningxin Wang † , and Ningyan Xu · 2026
Read Reconfiguration of Nowhere-zero Flows by Daniel W. Cranston, Jiaao Li † , Bo Su † , Zhouningxin Wang † , and Ningyan Xu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24685.txt.
Introduction
Daniel Cranston, Jiaao Li, Bo Su, Zhouningxin Wang, and Ningyan Xu study when nowhere zero flows on a graph can be reshaped into one another. A flow assigns group values to edges so that nothing cancels at any vertex. Two flows count as adjacent when they differ only along a single cycle. A graph is flow connected when chains of such small steps link every pair of its flows.
Cranston and colleagues first characterise the graphs that are flow connected for the group of order three, in both group and integer versions. They then show a reduction: checking all two edge connected graphs reduces to checking cubic ones. All cubic bipartite graphs prove flow connected for the group of order four. The team also constructs cubic graphs on both sides of that question. The results pin down exactly where small step reconfiguration always succeeds for small groups.
Catalog record
| CREATOR | Daniel W. Cranston, Jiaao Li † , Bo Su † , Zhouningxin Wang † , and Ningyan Xu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 120 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24685
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reconfiguration of Nowhere-zero Flows Daniel W. Cranston, Jiaao Li † , Bo Su † , Zhouningxin Wang † , and Ningyan Xu Abstract Fix an abelian group A A , a graph G G , and nowhere-zero A A -flows f ′ f^{\prime} and f ′′ f^{\prime\prime} on G G . Now f ′ f^{\prime} and f ′′ f^{\prime\prime} are A A -flow-adjacent if there exists a cycle C C in G G such that f ′ ( e ) − f ′′ ( e ) = 0 f^{\prime}(e)-f^{\prime\prime}(e)=0 for all edges e ∉ E ( C ) e\notin E(C) . And f ′ f^{\prime} and f ′′ f^{\prime\prime} are A A -flow-equivalent if there exists a sequence f 0 , … , f s f_{0},\ldots,f_{s} of A A -flows such that f 0 = f ′ f_{0}=f^{\prime} , f s = f ′′ f_{s}=f^{\prime\prime} , and f i f_{i} and f i − 1 f_{i-1} are A A -flow-adjacent for all i ∈ [ s ] i\in[s] . Given a group A A , we seek conditions on a graph G G such that all A A -flows on G G are pairwise A A -flow-equivalent; in this case, we say that G G is A A -flow-connected . Analogously, we define k k -flow-connectedness for nowhere-zero (integer) k k -flows. The notions of A A -flow-connectedness and k k -flow-connectedness were first investigated by Esperet et al., who showed, among other results, that every 2 2 -edge-connected graph is A A -flow-connected whenever A = ℤ 2 8 A=\mathbb{Z}_{2}^{8} or | A | ⩾ 1.15 × 10 694 |A|\geqslant 1.15\times 10^{694} . In this paper, we first characterize the graphs that are ℤ 3 \mathbb{Z}_{3} -flow-connected and that are 3 3 -flow-connected. We show that every 2-edge-connected graph is A A -flow-connected if and only if this is true for every 2-edge-connected cubic graphs. We show that all cubic bipartite graphs are ℤ 4 \mathbb{Z}_{4} -flow-connected, and construct other cubic graphs that are and are not ℤ 4 \mathbb{Z}_{4} -flow-connected. We conjecture that every Eulerian graph is k k -flow-connected and A A -flow-connected whenever k k or | A | |A| is at least 4; and provide evidence for this conjecture. Finally, we consider 4 4 -edge-connected graphs G G . Here, we show that G G is A A -flow-connected whenever | A | ⩾ 5.3 × 10 6 |A|\geqslant 5.3\times 10^{6} . 1 Introduction Fix a graph G and an abelian group 1 1 1 All abelian groups in this paper are finite, except when we explicitly specify the integers \mathbb{Z} . Sometimes we state this explicitly, but not always. A . An A -flow on G is an ordered pair (D,f) , consisting of an orientation D of G and a function f:E(G)\to A such that \sum_{e\in E_{D}^{+}(v)}f(e)-\sum_{e\in E_{D}^{-}(v)}f(e)=0_{A} for every vertex v , where E_{D}^{+}(v) and E_{D}^{-}(v) denote, respectively, the sets of edges directed out of and into v . Informally, we require that “flow in equals flow out” at each vertex. An A -flow is nowhere-zero if f(e)\neq 0_{A} for each edge e . Tutte defined nowhere-zero flows in the 1940s and proved that every planar graph is k -face-colorable if and only if it has a nowhere-zero \mathbb{Z}_{k} -flow. Motivated in part by this duality, he conjectured 2 2 2 In fact, Tutte phrased his conjectures in terms of integer-valued (rather than group-valued) flows, which we define soon. But he also proved the equivalence of the two formulations. the following. Conjecture 1.1 . The 3 statements below all hold. • Every 2-edge-connected graph has a nowhere-zero \mathbb{Z}_{5} -flow. • Every 2-edge-connected graph with no Petersen minor has a nowhere-zero \mathbb{Z}_{4} -flow. • Every 4-edge-connected graph has a nowhere-zero \mathbb{Z}_{3} -flow. These 3 conjectures are all more than 50 years old, and nowhere-zero flows have played a central role in structural and chromatic graph theory since they were posed. Despite some beautiful partial results [ 6 , 10 , 9 ] , all 3 conjectures remain open. Given a graph G and two proper k -colorings \alpha and \beta , the problem of k -coloring reconfiguration seeks to transform \alpha to \beta by changing the color of one vertex at a time, requiring that each intermediate k -coloring is again proper. This topic has close ties to Glauber dynamics and sampling a random proper k -coloring. Work in this area goes back many years, but it has received a more unified treatment starting with the dissertation of Cereceda [ 2 ] . Recently, Esperet et al. [ 4 ] initiated the study of reconfiguration of nowhere-zero flows. Now in each reconfiguration step, we may change the flow values on some cycle; here and throughout a cycle is a connected 2-regular graph. (This definition extends Tutte’s duality in planar graphs between flows and face colorings.) Given a graph G , an abelian group A , and A -flows \alpha,\beta , we again ask whether we can reconfigure \alpha into \beta . More generally, we seek conditions on G and A that allow us to transform every A -flow on G into every other A -flow. This motivates the following definitions. We consider two A -flows (D,f) and (D^{\prime},f^{\prime}) to be the same if for every edge e with D(e)=D^{\prime}(e) we have f(e)=f^{\prime}(e) , and for every edge e with D(e)=-D^{\prime}(e) we have f(e)+f^{\prime}(e)=0_{A} . Due to the definition of “same”, the orientation of a flow is typically unimportant, and we generally omit it; but we do consider the orientation fixed (across different flows). Nearly all flows considered in this paper are nowhere-zero; therefore, we typically write \bm{A} -flows or \bm{k} -flows (defined below), and will explicitly indicate when flows are allowed to take the value 0. Two A -flows f^{\prime} and f^{\prime\prime} on a graph G are A -flow-adjacent if there exists a cycle C in G such that f^{\prime}(e)=f^{\prime\prime}(e) for all e\notin E(C) . And f^{\prime} and f^{\prime\prime} are A -flow-equivalent if there exists a sequence f_{0},\ldots,f_{s} , with f^{\prime}=f_{0} and f^{\prime\prime}=f_{s} , of A -flows on G such that f_{i} and f_{i-1} are A -flow-adjacent for each i\in[s] . A graph G is A -flow-connected if all A -flows on G are pairwise A -flow-equivalent. Now the A -flow reconfiguration graph of G , denoted \mathcal{F}(G,A) , has as its vertices the A -flows on G , and two vertices are adjacent if and only if the corresponding flows are A -flow-adjacent. 3 3 3 If G has no A -flow, i.e. \mathcal{F}(G,A) is empty, then we say that G is indeed A -flow-connected. But this is a minor point, and it will rarely matter. For A=\mathbb{Z} , a nowhere-zero k -flow is an integer flow (D,f) satisfying 0<|f(e)|<k for all e\in E(G) . For each positive integer k , we analogously define k -flow-adjacency , k -flow-equivalence , k -flow-connectedness , and k -flow reconfiguration graph \mathcal{F}(G,k) . Given a k -flow on a graph G , it is easy to get a \mathbb{Z}_{k} -flow by taking each flow value modulo k . The other direction is less obvious, but Tutte proved it: a graph G has