Integer Flows on Cyclic Covers of Graphs

Abstract

Graph covers preserve the local structure of a graph while allowing its global structure to change substantially. In this paper, we study how such changes in cyclic covers affect nowhere-zero flow properties. For a fixed integer $\ell \ge 2$, we show that for every bridgeless graph $G$, there exists an $\ell$-fold cyclic cover of $G$ that admits a nowhere-zero $3$-flow if $\ell$ is even and a nowhere-zero $4$-flow if $\ell$ is odd. These bounds are best possible in general. For odd $\ell$, we further investigate which bridgeless graphs admit an $\ell$-fold cyclic cover with a nowhere-zero $3$-flow.

arXiv comment14 pages, 1 figure