All 4-Edge-Connected HHD-Free Graphs are Z(3)-Connected

作者：Fukunaga Takuro^*

来源：Graphs and Combinatorics, 2011, 27(5): 647-659.

DOI：10.1007/s00373-010-0995-9

• Edge-connectivity
• HHD-free graph
• Nowhere-zero flow
• Z(3)-Connectivity

An undirected graph G = (V, E) is called Z(3)-connected if for all b : V -> Z(3) with Sigma(nu is an element of V) b(v) = 0, an orientation D = (V, A) of G has a Z(3)-valued nowhere-zero flow f : A -> Z(3)-{0} such that Sigma(e is an element of delta+(nu)) f (e) - Sigma(e is an element of delta-(nu)) f (e) = b(nu) for all nu is an element of V. We show that all 4-edge-connected HHD-free graphs are Z3-connected. This extends the result due to Lai (Graphs Comb 16:165-176, 2000), which proves the Z(3)-connectivity for 4-edge-connected chordal graphs.

• 出版日期2011-9