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 Rd 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). The d-dimensional flow number of a bridgeless graph G, denoted by ϕd(G) , is the minimum of the real numbers r such that G admits an (r, d)-NZF. 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).

On d-dimensional nowhere-zero r-flows on a graph / Mattiolo, D., Mazzuoccolo, G., Rajnik, J., Tabarelli, G.. - In: EUROPEAN JOURNAL OF MATHEMATICS. - ISSN 2199-675X. - 9:4(2023), pp. 1-12. [10.1007/s40879-023-00694-1]

On d-dimensional nowhere-zero r-flows on a graph

Mazzuoccolo G.;Tabarelli G.
2023

Abstract

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 Rd 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). The d-dimensional flow number of a bridgeless graph G, denoted by ϕd(G) , is the minimum of the real numbers r such that G admits an (r, d)-NZF. 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).
2023
9
4
1
12
On d-dimensional nowhere-zero r-flows on a graph / Mattiolo, D., Mazzuoccolo, G., Rajnik, J., Tabarelli, G.. - In: EUROPEAN JOURNAL OF MATHEMATICS. - ISSN 2199-675X. - 9:4(2023), pp. 1-12. [10.1007/s40879-023-00694-1]
Mattiolo, D.; Mazzuoccolo, G.; Rajnik, J.; Tabarelli, G.
File in questo prodotto:
File Dimensione Formato  
accepted_revisionEJM.pdf

Open access

Tipologia: AO - Versione originale dell'autore proposta per la pubblicazione
Licenza: [IR] other-oa
Dimensione 322.59 kB
Formato Adobe PDF
322.59 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1411491
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact