On Mod $(2s+1)$-Orientations of Graphs
Ping Li, Hong‐Jian Lai · SIAM Journal on Discrete Mathematics · 2014
An orientation of a graph $G$ is a mod (2p+1)-orientation if, under this orientation, the net out-degree at every vertex is congruent to zero mod 2p+1. If, for any function $b: V(G) \rightarrow \mathbb Z_{2p+1}$ satisfying $\sum_{v \in V(G)} b(v) \equiv 0$ (mod 2p+1), $G$ always has an orientation $D$ such that the net out-degree at every vertex $v$ is congruent to $b(v)$ mod 2p+1, then $G$ is strongly $\mathbb Z_{2p+1}$-connected. The graph $G'$ obtained from $G$ by contracting all nontrivial subgraphs that are strongly $\mathbb Z_{2s+1}$-connected is called the $\mathbb Z_{2s+1}$-reduction of $G$. Motivated by a minimum degree condition of Barat and Thomassen [J. Graph Theory, 52 (2006), pp. 135--146], and by the Ore conditions of Fan and Zhou [SIAM J. Discrete Math., 22 (2008), pp. 288--294] and of Luo et al. [European J. Combin., 29 (2008), pp. 1587--1595] on $\mathbb Z_3$-connected graphs, we prove that for a simple graph $G$ on $n$ vertices, and for any integers $s > 0$ and real numbers $\alpha, \beta$ with $0 < \alpha < 1$, if for any nonadjacent vertices $u, v \in V(G)$, $d_G(u) + d_G(v) \ge \alpha n + \beta$, then there exists a finite family ${\cal {F}}(\alpha,s)$ of nonstrongly $\mathbb Z_{2s+1}$-connected graphs such that either $G$ is strongly $\mathbb Z_{2s+1}$-connected or the $\mathbb Z_{2s+1}$-reduction of $G$ is in ${\cal {F}}(\alpha,s)$.