pith. sign in

arxiv: 1307.1562 · v4 · pith:BHA63IYLnew · submitted 2013-07-05 · 🧮 math.CO · cs.DM

Nowhere-zero flows on signed regular graphs

classification 🧮 math.CO cs.DM
keywords flowoverlinefactorgraphsintegersignedspectrumcubic
0
0 comments X
read the original abstract

We study the flow spectrum ${\cal S}(G)$ and the integer flow spectrum $\overline{{\cal S}}(G)$ of signed $(2t+1)$-regular graphs. We show that if $r \in {\cal S}(G)$, then $r = 2+\frac{1}{t}$ or $r \geq 2 + \frac{2}{2t-1}$. Furthermore, $2 + \frac{1}{t} \in {\cal S}(G)$ if and only if $G$ has a $t$-factor. If $G$ has a 1-factor, then $3 \in \overline{{\cal S}}(G)$, and for every $t \geq 2$, there is a signed $(2t+1)$-regular graph $(H,\sigma)$ with $ 3 \in \overline{{\cal S}}(H)$ and $H$ does not have a 1-factor. If $G$ $(\not = K_2^3)$ is a cubic graph which has a 1-factor, then $\{3,4\} \subseteq {\cal S}(G) \cap \overline{{\cal S}}(G)$. Furthermore, the following four statements are equivalent: (1) $G$ has a 1-factor. (2) $3 \in {\cal S}(G)$. (3) $3 \in \overline{{\cal S}}(G)$. (4) $4 \in \overline{{\cal 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.