Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Circular flows in mono-directed signed graphs

Abstract : In this paper the concept of circular r-flows in a mono-directed signed graph (G, σ) is introduced. That is a pair (D, f), where D is an orientation on G and f : E(G) → (−r, r) satisfies that |f (e)| ∈ [1, r − 1] for each positive edge e and |f (e)| ∈ [0, r 2 − 1] ∪ [ r 2 + 1, r) for each negative edge e, and the total inflow equals the total out-flow at each vertex. The circular flow index of a signed graph (G, σ) with no positive bridge, denoted Φ c (G, σ), is the minimum r such that (G, σ) admits a circular r-flow. This is the dual notion of circular colorings and circular chromatic numbers of signed graphs recently introduced in [Circular chromatic number of signed graphs. R. Naserasr, Z. Wang, and X. Zhu. Electronic Journal of Combinatorics, 28(2)(2021), #P2.44], and is distinct from the concept of circular flows in bi-directed graphs associated to signed graphs studied in the literature. We give several equivalent definitions, study basic properties of circular flows in mono-directed signed graphs, and explore relations with flows in graphs. Then we focus on upper bounds on Φ c (G, σ) in terms of the edge-connectivity of G. Tutte's 5-flow conjecture is equivalent to saying that every 2-edge-connected signed graph has circular flow index at most 10. We show that if (G, σ) is a 3-edge-connected (4-edge-connected, respectively) signed graph, then Φ c (G, σ) ≤ 6 (Φ c (G, σ) ≤ 4, respectively). For k ≥ 2, if (G, σ) is (3k − 1)-edge-connected, then Φ c (G, σ) ≤ 2k k−1 ; if (G, σ) is 3k-edge-connected, then Φ c (G, σ) < 2k k−1 ; and if (G, σ) is (3k + 1)-edge-connected, then Φ c (G, σ) ≤ 4k+2 2k−1. When restricted to the class of signed Eulerian graphs, if (G, σ) is (6k − 2)-edgeconnected, then Φ c (G, σ) ≤ 4k 2k−1. Applying this on planar graphs we conclude that every signed bipartite planar graph of negative-girth at least 6k − 2 admits a homomorphism to C −2k. For the particular values of r k = 2k k−1 , and when restricted to two natural subclasses of signed graphs, the existence of a circular r k-flow is strongly connected with the existence of a modulo k-orientation, and in case of planar graphs, based on duality, with the homomorphisms to C −k .
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Reza Naserasr Connect in order to contact the contributor
Submitted on : Sunday, November 6, 2022 - 12:16:17 AM
Last modification on : Wednesday, November 9, 2022 - 4:09:06 AM


Files produced by the author(s)


  • HAL Id : hal-03840742, version 1



Jiaao Li, Reza Naserasr, Zhouningxin Wang, Xuding Zhu. Circular flows in mono-directed signed graphs. 2022. ⟨hal-03840742⟩



Record views


Files downloads