All 4-Edge-Connected HHD-Free Graphs are {mathbb{Z}_3}-Connected |
| |
Authors: | Takuro Fukunaga |
| |
Affiliation: | 1. Graduate School of Informatics, Kyoto University, Kyoto, Japan
|
| |
Abstract: | An undirected graph G = (V, E) is called mathbbZ3{mathbb{Z}_3}-connected if for all b: V ? mathbbZ3{b: V rightarrow mathbb{Z}_3} with ?v ? Vb(v)=0{sum_{v in V}b(v)=0}, an orientation D = (V, A) of G has a mathbbZ3{mathbb{Z}_3}-valued nowhere-zero flow f: A? mathbbZ3-{0}{f: Arightarrow mathbb{Z}_3-{0}} such that ?e ? d+(v)f(e)-?e ? d-(v)f(e)=b(v){sum_{e in delta^+(v)}f(e)-sum_{e in delta^-(v)}f(e)=b(v)} for all v ? V{v in V}. We show that all 4-edge-connected HHD-free graphs are mathbbZ3{mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the mathbbZ3{mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|