Reconfiguration of Nowhere-zero Flows

Abstract

Fix an abelian group $A$, a graph $G$, and nowhere-zero $A$-flows $f^{\prime }$ and $f^{\prime \prime }$ on $G$. Now $f^{\prime }$ and $f^{\prime \prime }$ are \emph{$A$-flow-adjacent} if there exists a cycle $C$ in $G$ such that $f^{\prime }(e)-f^{\prime \prime }(e)=0$ for all edges $e\notin E(C)$. And $f^{\prime }$ and $f^{\prime \prime }$ are \emph{$A$-flow-equivalent} if there exists a sequence $f_0,\dots ,f_s$ of $A$-flows such that $f_0=f^{\prime }$, $f_s=f^{\prime \prime }$, and $f_i$ and $f_{i-1}$ are $A$-flow-adjacent for all $i\in [s]$. Given a group $A$, we seek conditions on a graph $G$ such that all $A$-flows on $G$ are pairwise $A$-flow-equivalent; in this case, we say that $G$ is \emph{$A$-flow-connected}. Analogously, we define $k$-flow-connectedness for nowhere-zero (integer) $k$-flows. The notions of $A$-flow-connectedness and $k$-flow-connectedness were first investigated by Esperet et al., who showed, among other results, that every $2$-edge-connected graph is $A$-flow-connected whenever $A={\mathbb{Z}}_2^8$ or $|A|\ge 1.15\times 10^{694}$. In this paper, we first characterize the graphs that are ${\mathbb{Z}}_3$-flow-connected and that are $3$-flow-connected. We show that every 2-edge-connected graph is $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 ${\mathbb{Z}}_4$-flow-connected, and construct other cubic graphs that are and are not ${\mathbb{Z}}_4$-flow-connected. We conjecture that every Eulerian graph is $k$-flow-connected and $A$-flow-connected whenever $k$ or $|A|$ is even; and provide evidence for this conjecture. Finally, we consider $4$-edge-connected graphs $G$. Here, we show that $G$ is $A$-flow-connected whenever $|A|\ge 5.3\times 10^6$.

34 pages, 6 figures