Cited by

- BibTex
- RIS
- TXT

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_1T_2 · · · T_k$ in $G$ such that for $1 ≤ i ≤ k − 1,$ $|E(T_i) ∩ E(T_{i+1})| = 1$ and $E(T_i) ∩ E(T_j ) = ∅$ if $j > i + 1.$ Two edges $e,$ $e′ ∈ E(G)$ are triangularly connected if there is a triangle-path $T_1, T_2, · · · , T_k$ in $G$ such that $e ∈ E(T_1)$ and $e ′ ∈ E(T_k).$ Two edges $e,$ $e′ ∈ 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.

}, issn = {}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/aam/20622.html} }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_1T_2 · · · T_k$ in $G$ such that for $1 ≤ i ≤ k − 1,$ $|E(T_i) ∩ E(T_{i+1})| = 1$ and $E(T_i) ∩ E(T_j ) = ∅$ if $j > i + 1.$ Two edges $e,$ $e′ ∈ E(G)$ are triangularly connected if there is a triangle-path $T_1, T_2, · · · , T_k$ in $G$ such that $e ∈ E(T_1)$ and $e ′ ∈ E(T_k).$ Two edges $e,$ $e′ ∈ 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.

*Annals of Applied Mathematics*.

*33*(4). 428-438. doi: