Vector Flows and Integer Flows
Yi Wang, Jian Cheng, Rong Luo, Cun‐Quan Zhang · SIAM Journal on Discrete Mathematics · 2015
A vector ${S}^d$-flow is a flow whose flow values are vectors in $S^d$, where $S^d$ is the set of all unit vectors in $\mathbb{R}^{d+1}$. Jain [Open Problem Garden, http://www.openproblemgarden.org/op/unit_vector_flows (2007)] and Thomassen [J. Combin. Theory Ser. B., 108 (2014), pp. 81--91] proved that a graph has a vector $S^1$-flow if it has a nowhere-zero integer 3-flow. Thomassen [J. Combin. Theory Ser. B., 108 (2014), pp. 81--91] pointed out that a graph admitting a vector $S^1$-flow may not necessarily admit a nowhere-zero integer 3-flow and presented a family of examples showing that the converse is not true. The rank of a vector $S^1$-flow $( D,\bm {f} )$ is defined as the rank of linear space generated by all balanced vectors ${\bm{\epsilon}}(v)=(\epsilon_1(v), \epsilon_2(v), \ldots, \epsilon_b(v))$ for all $v \in V(G)$, where $\epsilon_i(v)$ is the difference between the number of outgoing edges with flow value ${\bm \alpha}_i$ from $v$ and the number of ingoing edges with the same flow value to $v$. In this paper, we prove that $G$ admits a nowhere-zero integer 3-flow if $G$ admits a vector $S^{1}$-flow with rank at most two. This result is sharp since there are examples that admit vector $S^1$-flows with rank at least 3, but no nowhere-zero integer 3-flows.