Nowhere-zero 3-flows and Z(3)-connectivity of a family of graphs

作者：Yan Jin^*

来源：Discrete Mathematics, 2011, 311(17): 1988-1994.

DOI：10.1016/j.disc.2011.05.011

• Degree condition
• Nowhere-zero 3-flow
• Z(3)-connected

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. Jaeger et al. [F. Jaeger, N. Linial, C. Payan, M. Tarsi, Group connectivity of graphs-a nonhomogeneous analogue of Nowhere-zero flow properties, J. Combin. Theory, Ser. B 56 (1992) 165-182] conjectured that every 5-edge-connected graph is Z(3)- connected. Let G be a simple connected graph with n vertices. It is proved in this paper that if d(u) + d(v) >= n for each pair of vertices u. v with distance two, then (1) G admits a nowhere-zero 3-flow if and only if G is none of 7 excluded graphs; (2)G is Z(3)-connected if and only if G is none of 15 excluded graphs. The first theorem strengthens an early result by Fan et al. [ G. Fan, C. Zhou. Ore condition and Nowhere-zero 3-flows, SIAM J. Discrete Math., 22 (2008) 288-294] and the second theorem strengthens an early result by Luo, et al. [ R. Luo, R. Xu, J.H. Yin, G.X. Yu, Ore-condition and Z(3)-connectivity, European J. Combin., 29 (2008) 1587-1595].

• 出版日期2011-9-6
• 单位山东大学