Abstract:We initiate the study of nowhere-zero flow reconfiguration. The natural question is whether any two nowhere-zero $k$-flows of a given graph $G$ are connected by a sequence of nowhere-zero $k$-flows of $G$, such that any two consecutive flows in the sequence differ only on a cycle of $G$.
We study this problem in the setting of integer flows and group flows, and prove a number of positive and negative results.
* The natural reconfiguration variant of Tutte's 5-flow conjecture, stating that any two nowhere-zero 5-flows in any 2-edge-connected graph are connected, is false in the group and integer cases.
* All nowhere-zero $\mathbb{Z}_2^8$-flows of every 2-edge-connected graph are connected and for every sufficiently large abelian group $A$, all nowhere-zero $A$-flows of every 2-edge-connected graph are connected.
* The group structure affects the answer, contrary to the existence problem for nowhere-zero flows.
* We highlight a duality with recoloring in planar graphs and deduce that any two nowhere-zero 7-flows in a planar graph are connected, among other results.
* For every 2-edge-connected graph $G$, there is an integer $k$ such that all nowhere-zero $k$-flows of $G$ are connected.
From: Louis Esperet [view email]
[v1]
Fri, 19 Dec 2025 08:34:36 UTC (150 KB)
[v2]
Tue, 21 Apr 2026 07:31:27 UTC (194 KB)
[v3]
Mon, 4 May 2026 16:01:47 UTC (194 KB)
[v4]
Fri, 3 Jul 2026 07:14:08 UTC (194 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。