Graphic additive bases and graph flows
Abstract
Nash--Williams's orientation theorem converts undirected edge-connectivity into directed connectivity. We extend it to prescribed outdegrees modulo q, whose residues must sum to the number of edges modulo q. For integers q,k≥1, every such prescription has a realization with at least k edges in each direction across each nontrivial cut if the graph is (2q+2k−2)-edge-connected or contains q+2k−1 edge-disjoint spanning trees. The method combines a cycle-space approximation bound with rounding that preserves the imbalance across every cut. Fractional spanning-tree packing gives an exact criterion: every compatible prescription has a strongly connected realization if and only if the fractional packing number exceeds q. This yields a polynomial-time recognition test. With no directed connectivity requirement, q disjoint spanning trees suffice, proving Hasanvand's prescribed-residue conjecture. For every odd prime p, this proves the conjectured statement that the union of p graphic bases over the field with p elements is an additive basis. For every integer p≥5, the theorem and the counterexamples of Han, Li, Wu and Zhang give the exact edge-connectivity threshold 4p+2 for a modulo-(2p+1) orientation. We also show that every six-edge-connected graph has circular flow number strictly below three, as conjectured by Li, Thomassen, Wu and Zhang. For three-flow-critical graphs on n vertices and m edges, we improve the previous general bound m≤4n−10 to m≤3n−6, and to m≤3n−7 when n≥5. Further applications include Seymour's six-flow theorem, star decompositions, antisymmetric flows, and signed modular orientations.
Related
- Additive bases and the zero-sum invariant N(G) for groups Cp⊕ Cnp
- On additive bases of finite abelian groups
- Diameter and radius of an additive-multiplicative graph
- HARMONIA: Interpretable Graph Learning through Mixtures of Neural Bases
- Additive Quasi-isometry via rooted graph partitions and layering partition
BibTeX
@misc{jafari2026graphic,
title = {{Graphic additive bases and graph flows}},
author = {Amir Jafari},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07034},
eprint = {2610.07034},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07034},
}
RIS
TY - UNPB
TI - Graphic additive bases and graph flows
AU - Amir Jafari
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.07034
UR - https://arxiv.org/abs/2610.07034
AB - Nash--Williams's orientation theorem converts undirected edge-connectivity into directed connectivity. We extend it to prescribed outdegrees modulo q, whose residues must sum to the number of edges modulo q. For integers q,k≥1, every such prescription has a realization with at least k edges in each direction across each nontrivial cut if the graph is (2q+2k−2)-edge-connected or contains q+2k−1 edge-disjoint spanning trees. The method combines a cycle-space approximation bound with rounding that preserves the imbalance across every cut. Fractional spanning-tree packing gives an exact criterion: every compatible prescription has a strongly connected realization if and only if the fractional packing number exceeds q. This yields a polynomial-time recognition test. With no directed connectivity requirement, q disjoint spanning trees suffice, proving Hasanvand's prescribed-residue conjecture. For every odd prime p, this proves the conjectured statement that the union of p graphic bases over the field with p elements is an additive basis. For every integer p≥5, the theorem and the counterexamples of Han, Li, Wu and Zhang give the exact edge-connectivity threshold 4p+2 for a modulo-(2p+1) orientation. We also show that every six-edge-connected graph has circular flow number strictly below three, as conjectured by Li, Thomassen, Wu and Zhang. For three-flow-critical graphs on n vertices and m edges, we improve the previous general bound m≤4n−10 to m≤3n−6, and to m≤3n−7 when n≥5. Further applications include Seymour's six-flow theorem, star decompositions, antisymmetric flows, and signed modular orientations.
ER -