Nowhere-zero flows on signed regular graphs

Abstract

We study the flow spectrum $\mathcal{S}(G)$ and the integer flow spectrum $\overline{\mathcal{S}}(G)$ of signed $(2t+1)$-regular graphs. We show that if $r\in \mathcal{S}(G)$, then $r=2+\frac{1}{t}$ or $r\ge 2+\frac{2}{2t-1}$. Furthermore, $2+\frac{1}{t}\in \mathcal{S}(G)$ if and only if $G$ has a $t$-factor. If $G$ has a 1-factor, then $3\in \overline{\mathcal{S}}(G)$, and for every $t\ge 2$, there is a signed $(2t+1)$-regular graph $(H,\sigma )$ with $3\in \overline{\mathcal{S}}(H)$ and $H$ does not have a 1-factor. If $G$ $(\ne K_2^3)$ is a cubic graph which has a 1-factor, then $\{3,4\}\subseteq \mathcal{S}(G)\cap \overline{\mathcal{S}}(G)$. Furthermore, the following four statements are equivalent: (1) $G$ has a 1-factor. (2) $3\in \mathcal{S}(G)$. (3) $3\in \overline{\mathcal{S}}(G)$. (4) $4\in \overline{\mathcal{S}}(G)$. There are cubic graphs whose integer flow spectrum does not contain 5 or 6, and we construct an infinite family of bridgeless cubic graphs with integer flow spectrum $\{3,4,6\}$. We show that there are signed graphs where the difference between the integer flow number and the flow number is greater than or equal to 1, disproving a conjecture of Raspaud and Zhu. The paper concludes with a proof of Bouchet's 6-flow conjecture for Kotzig-graphs.

24 pages, 4 figures; final version; to appear in European J. Combinatorics

References in corpus (1)

• Nowhere-zero flows on signed eulerian graphs

Cited by in corpus (1)

• Flows on signed graphs without long barbells