On strongly -connected graphs

详细信息    查看全文

• 作者：Hong-Jian Lai^a ; ^b ; ^{hjlai@math.wvu.edu" class="auth_mail} ; ^{hongjianlai@gmail.com" class="auth_mail} ; Yanting Liang^c ; ^{yanting.liang@uwc.edu" class="auth_mail} ; Juan Liu^d ; ^{liujuan1999@126.com" class="auth_mail} ; Jixiang Meng^a ; ^{mjx@xju.edu.cn" class="auth_mail} ; Zhengke Miao^e ; ^{zkmiao@jsnu.edu.cn" class="auth_mail} ; Yehong Shao^f ; ^{shaoy@ohio.edu" class="auth_mail} ; Zhao Zhang^a ; ^{hxhzz@sina.com" class="auth_mail}
• 关键词：mod(2s+1)mod(2s+1)-orientations ; Nowhere zero flows ; Integer flows ; Unitary ZmZm-flows ; Strongly Z2s+1Z2s+1-connectedness ; Group connectivity
• 刊名：Discrete Applied Mathematics
• 出版年：10 September 2014
• 年：2014
• 卷：174
• 期：Complete
• 页码：73-80
• 全文大小：469 K

文摘

An orientation of a graph G$G$ is a mod(2s+1)$mod(2s+1)$-orientation if under this orientation, the net out-degree at every vertex is congruent to zero mod(2s+1)$mod(2s+1)$. If for any function b:V(G)→Z_2s+1$b:V\left(G\right)\to {\mathbb{Z}}_{2s+1}$ satisfying ${\sum }_{v\in V\left(G\right)}b\left(v\right)\equiv 0(mod2s+1)$, G$G$ always has an orientation D$D$ such that the net out-degree at every vertex v$v$ is congruent to b(v)mod(2s+1)$b\left(v\right)mod(2s+1)$, then G$G$ is strongly Z_2s+1${\mathbb{Z}}_{2s+1}$-connected. In this paper, we prove that a connected graph has a mod(2s+1)$mod(2s+1)$-orientation if and only if it is a contraction of a (2s+1)$(2s+1)$-regular bipartite graph. We also proved that every (4s−1)$(4s-1)$-edge-connected series–parallel graph is strongly Z_2s+1${\mathbb{Z}}_{2s+1}$-connected, and every simple 4p$4p$-connected chordal graph is strongly Z_2s+1${\mathbb{Z}}_{2s+1}$-connected.