Nowhere-zero flow reconfiguration
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911643749842944 |
|---|---|
| author | Esperet, Louis Hendrey, Kevin Lagoutte, Aurélie Marseloo, Margaux Norin, Sergey Steiner, Raphael |
| author_facet | Esperet, Louis Hendrey, Kevin Lagoutte, Aurélie Marseloo, Margaux Norin, Sergey Steiner, Raphael |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_17342 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nowhere-zero flow reconfiguration Esperet, Louis Hendrey, Kevin Lagoutte, Aurélie Marseloo, Margaux Norin, Sergey Steiner, Raphael Combinatorics Discrete Mathematics 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. |
| title | Nowhere-zero flow reconfiguration |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2512.17342 |