Realizing degree sequences with ${\mathcal{S}}_3$-connected graphs

Abstract

A graph $G$ is ${\mathcal{S}}_3$-connected if, for any mapping ${\hat{I}}^2:V(G)\mapsto {\mathbb{Z}}_3$ with ${\sum }_{v\in V(G)}{\hat{I}}^2(v)\equiv 0(\mathrm{mod}3)$, there exists a strongly connected orientation $D$ satisfying $d_D^{+}(v)-d_D^{-}(v)\equiv {\hat{I}}^2(v)(\mathrm{mod}3)$ for any $v\in V(G)$. It is known that ${\mathcal{S}}_3$-connected graphs are contractible configurations for the property of flow index strictly less than three. In this paper, we provide a complete characterization of graphic sequences that have an ${\mathcal{S}}_3$-connected realization: A graphic sequence $\ddot{I}€=(d_1,\dots ,d_n)$ has an ${\mathcal{S}}_3$-connected realization if and only if $\min \{d_1,\dots ,d_n\}\ge 4$ and ${\sum }_{i=1}^n{d}_i\ge 6n-4$. Consequently, every graphic sequence $\ddot{I}€=(d_1,\dots ,d_n)$ with $\min \{d_1,\dots ,d_n\}\ge 6$ has a realization $G$ with flow index strictly less than three. This supports a conjecture of Li, Thomassen, Wu and Zhang [European J. Combin., 70 (2018) 164-177] that every $6$-edge-connected graph has flow index strictly less than three.

19 pages, 6 figures