Flow number and circular flow number of signed cubic graphs

Main Article Content

Anna Kompišová Edita Máčajová


Let $\Phi(G,\sigma)$ and $\Phi_c(G,\sigma)$ denote the flow number and the circular flow number of a flow-admissible signed graph $(G,\sigma)$, respectively. It is known that $\Phi(G) = \lceil \Phi_c(G)\rceil $ for every unsigned graph $G$.
Based on this fact Raspaud and Zhu in 2011 conjectured that $\Phi(G,\sigma) - \Phi_c(G,\sigma) < 1$ holds also for every flow-admissible signed graph $(G,\sigma)$. This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory.
For cubic graphs we show that $\Phi(G,\sigma) =3$ if and only if $\Phi_c(G,\sigma) = 3$ and if $\Phi(G,\sigma) \in \{4,5\}$, then $4 \leq \Phi_c(G,\sigma) \leq \Phi(G,\sigma)$. We also prove that all pairs of flow number and circular flow number that fulfill these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless cubic signed graphs. Finally, we prove that all currently known graphs without nowhere-zero $5$-flow have flow number and circular flow number $6$ and propose several conjectures in this area.

Article Details

How to Cite
Kompišová, A., & Máčajová, E. (2019). Flow number and circular flow number of signed cubic graphs. Acta Mathematica Universitatis Comenianae, 88(3), 877-883. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1312/740