Realizing Degree Sequences with Graphs Having Nowhere-Zero 3-Flows
Rong Luo, Rui Xu, Wenan Zang, Cun‐Quan Zhang · SIAM Journal on Discrete Mathematics · 2008
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 eq (3^4,2)$, $(k,3^k)$, $(k^2,3^{k-1})$, where k is an odd integer.