Nowhere-zero Unoriented Flows in Hamiltonian Graphs
Saieed Akbari, Akbar Daemi, O. Hatami, Adel Javanmard, Abbas Mehrabian · 2016
An unoriented flow in a graph, is an assignment of real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. This is equivalent to a flow in a bidirected graph all of whose edges are extraverted. A nowhere-zero unoriented k-flow is an unoriented flow with values from the set {±1,...,±(k − 1)}. It has been conjectured that if a graph has a nowhere-zero unoriented flow, then it admits a nowhere-zero unoriented 6-flow. We prove that this conjecture is true for hamiltonian graphs, with 6 replaced by 12. ∗Keywords: Hamiltonian graph, nowhere-zero flow, unoriented flow, bidirected graph.