All 4-Edge-Connected HHD-Free Graphs are {\mathbb{Z}_3}-Connected |
| |
Authors: | Takuro Fukunaga |
| |
Institution: | 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: A\rightarrow \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 等数据库收录! |
|