Circular flow numbers of regular multigraphs
Eckhard Steffen · Journal of Graph Theory · 2001
The circular flow number F c (G) of a graph G = (V; E) is the minimum r 2 Q such that G admits a flow OE with 1 OE(e) r \\Gamma 1, for each e 2 E. We determine the circular flow number of some regular multigraphs. In particular, we characterize the bipartite (2t + 1)-regular graphs (t 1). Our results imply that there are gaps for possible circular flow numbers for (2t + 1)-regular graphs, e.g. there is no cubic graph G with 3 ! F c (G) ! 4. We further show that there are snarks with circular flow number arbitrary close to 4, answering a question of X. Zhu. 1 Introduction and basic definitions In this paper we consider multigraphs M = (V; E), with vertex set V and edge set E. Each edge is incident to precisely two different vertices, that is, we do not allow loops. An orientation D of M is an assignment of a direction to each edge, and for v 2 V , D + (v) (D \\Gamma (v)) is the set of edges whose head (tail) is incident to v. Let k 2 be a positive integer and OE : E \\Gamma! ...