2023/04/27 by Davide Mattiolo, Mattiolo, Davide, Giuseppe Mazzuoccolo +5 · 3 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2304.14231
openalex publication_date 2023/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A d-dimensional nowhere-zero r-flow on a graph G, an (r,d)-NZF from now on, is a flow where the value on each edge is an element of ℝd whose (Euclidean) norm lies in the interval [1,r-1]. Such a notion is a natural generalization of the well-known concept of circular nowhere-zero r-flow (i.e. d=1). For every bridgeless graph G, the 5-flow Conjecture claims that ϕ1(G)≤ 5, while a conjecture by Jain suggests that ϕd(G)=1, for all d ≥ 3. Here, we address the problem of finding a possible upper-bound also for the remaining case d=2. We show that, for all bridgeless graphs, ϕ2(G) ≤ 1 + √(5) and that the oriented 5-cycle double cover Conjecture implies ϕ2(G)≤ τ2, where τ is the Golden Ratio. Moreover, we propose a geometric method to describe an (r,2)-NZF of a cubic graph in a compact way, and we apply it in some instances. Our results and some computational evidence suggest that τ2 could be a promising upper bound for the parameter ϕ2(G) for an arbitrary bridgeless graph G. We leave that as a relevant open problem which represents an analogous of the 5-flow Conjecture in the 2-dimensional case (i.e. complex case).