2025/12/19 by Louis Esperet, Esperet, Louis, Hendrey, Kevin +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Advanced Topology and Set Theory
paper · doi:10.48550/arxiv.2512.17342
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 ℤ28-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.