Nowhere–zero bases for the nullspace of the incidence matrices of graphs

ABSTRACT

A nowhere-zero k-flow for a directed or undirected graph is a vector in the nullspace of the incidence matrix of the graph such that all the entries of the vector are from the set $\{\pm 1,\pm 2,\dots ,\pm (k-1\left)\right\}$. We consider the problem of finding a basis consisting of nowhere-zero k-flows for the nullspace of the incidence matrix. For a variety of graphs—including the complete graphs—we find such bases with k=2 or k=3. We prove that all directed graphs with no cut-edge have such a basis with k=12, and conjecture that 12 can be replaced with 5. If true, this would strengthen Tutte's celebrated conjecture on nowhere-zero 5-flows. For undirected graphs that have some nowhere-zero k-flow, we prove the existence of a basis of nowhere-zero 36-flows and conjecture that 36 can be replaced with 6.

KEYWORDS:

• Nowhere-zero k-flow
• zero sum flows
• nowhere zero basis
• basis for nullspace

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 05C21
• 05C78
• 05B20

Acknowledgments

The last author thanks the Institute for Research in Fundamental Sciences (IPM) in Tehran, Iran for its hospitality.

Disclosure statement

No potential conflict of interest was reported by the authors.