|
| Z3-CONNECTIVITY OF 4-EDGE-CONNECTED TRIANGULAR GRAPHS |
| Chuixiang Zhou |
| (Center for Discrete Math., Fuzhou University, Fuzhou 350002, Fujian, PR China) |
| DOI： |
| Abstract: |
| A graph $G$ is $k$-triangular if each of its edge is contained in at least $k$ triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1 T_2\cdots T_k$ in $G$ such that for $1\leq i\leq k-1, |E(T_i )\cap E(T_{i+1})|=1$ and
$E(T_i)\cap E(T_j)=\emptyset$ if $j>i+1$. Two edges $e,e'\in E(G)$ are triangularly connected if there is a triangle-path $T_1,T_2,\cdots, T_k$ in $G$ such that $e\in E(T_1)$ and $e'\in E(T_k)$. Two edges $e,e'\in E(G)$ are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph $G$ is ${\mathbb Z}_3$-connected, unless it has a triangularly connected component which is not ${\mathbb Z}_3$-connected but admits a nowhere-zero 3-flow. |
| Key words: ${\mathbb Z}_3$-connected; nowhere-zero 3-flow; triangular graphs |