Realizing Degree Sequences with Graphs Having Nowhere-Zero 3-Flows

Abstract

The following open problem was proposed by Archdeacon: Characterize all graphical sequences $\pi$ such that some realization of $\pi$ admits a nowhere-zero 3-flow. The purpose of this paper is to resolve this problem and present a complete characterization: A graphical sequence $\pi = (d_1,d_2,\dots,d_n)$ with minimum degree at least two has a realization that admits a nowhere-zero 3-flow if and only if $\pi \neq (3^4,2)$, $(k,3^k)$, $(k^2,3^{k-1})$, where k is an odd integer.