On Mod $(2s+1)$-Orientations of Graphs
Author(s) -
Ping Li,
HongJian Lai
Publication year - 2014
Publication title -
siam journal on discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.843
H-Index - 66
eISSN - 1095-7146
pISSN - 0895-4801
DOI - 10.1137/130920435
Subject(s) - combinatorics , mathematics , vertex (graph theory) , mod , connectivity , graph , simple graph , orientation (vector space) , degree (music) , discrete mathematics , physics , geometry , acoustics
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, \be...
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom