Additive bases and flows in graphs

DOI10.1016/J.ENDM.2017.06.066MaRDI QIDQ1689948zbMATH OpenOpenAlexFDO

Authors L. Esperet, Rémi de Joannis de Verclos, Tien-Nam Le, Stéphan Thomassé

Publication date 18 January 2018

Full work available at URL https://arxiv.org/abs/1701.03366

zbMATH Keywords

nowhere-zero flowsedge-connectivityadditive bases

Mathematics Subject Classification ID

Flows in graphs (05C21) Connectivity (05C40)

Abstract: It was conjectured by Jaeger, Linial, Payan, and Tarsi in 1992 that for any prime number $p$, there is a constant $c$ such that for any $n$, the union (with repetition) of the vectors of any family of $c$ linear bases of $mathbb{Z}_p^n$ forms an additive basis of $mathbb{Z}_p^n$ (i.e. any element of $mathbb{Z}_p^n$ can be expressed as the sum of a subset of these vectors). In this note, we prove this conjecture when each vector contains at most two non-zero entries. As an application, we prove several results on flows in highly edge-connected graphs, extending known results. For instance, assume that $pge3$ is a prime number and $vecG$ is a directed, highly edge-connected graph in which each arc is given a list of two distinct values in $mathbb{Z}_p$. Then $vecG$ has a $mathbb{Z}_p$-flow in which each arc is assigned a value of its own list.

Recommendations

• Additive bases and flows in graphs
• scientific article; zbMATH DE number 3904637
• Group flow, complex flow, unit vector flow, and the (2 + )-flow conjecture
• Nowhere-zero bases for the nullspace of the incidence matrices of graphs
• Nowhere-zero 3-flows and \(Z_{3}\)-connectivity of a family of graphs

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• A note on antisymmetric flows in graphs
• Additive bases of vector spaces over prime fields
• Antisymmetric flows and edge-connectivity
• Antisymmetric flows and strong colourings of oriented graphs
• Colorings and girth of oriented planar graphs
• Flows and generalized coloring theorems in graphs
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Matrix choosability
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• On the algebraic theory of graph colorings
• The weak 3-flow conjecture and the weak circular flow conjecture

Cited in

(1)

• Additive bases and flows in graphs

This page was built for publication: Additive bases and flows in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1689948)