Seminár z teórie grafov - Jozef Rajník (21.4.2022)
vo štvrtok 21.4.2022 o 9:50 hod. v miestnosti M/213
Prednášajúci: Jozef Rajnik
Názov: On d-dimensional nowhere-zero r-flows on a graph
Termín: 21.4.2022, 9:50 hod., M 213
Abstrakt:
A d-dimensional nowhere-zero r-flow on a graph G, an (r,d)-NZF for short, is a flow where the value on each edge is an element of R^d whose 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). In this paper, we mainly consider the parameter \phi_d(G), which 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 \phi_1(G) <= 5, while a conjecture by Kamal Jain suggests that \phi_d(G)=1, for all d >= 3. Here, we address the problem of finding a possible upper-bound in the case d = 2. We show that, for all bridgeless graphs, \phi_2(G) <= 1 + \sqrt{5} and that the oriented 5-Cycle Double Cover Conjecture implies \phi_2(G) <= \Phi^2, where \Phi is the Golden Ratio. Moreover, we discuss some connections between this problem and some other well-known conjectures. Finally, we focus our attention on the cubic case: 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.