Volume 33, Issue 4
$\mathbb{Z}_3$-Connectivity of 4-Edge-Connected Triangular Graphs

Chuixiang Zhou

Ann. Appl. Math., 33 (2017), pp. 428-438.

Published online: 2022-06

Export citation
  • 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_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.

  • AMS Subject Headings

05C21

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{AAM-33-428, author = {Zhou , Chuixiang}, title = {$\mathbb{Z}_3$-Connectivity of 4-Edge-Connected Triangular Graphs}, journal = {Annals of Applied Mathematics}, year = {2022}, volume = {33}, number = {4}, pages = {428--438}, 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_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} }
TY - JOUR T1 - $\mathbb{Z}_3$-Connectivity of 4-Edge-Connected Triangular Graphs AU - Zhou , Chuixiang JO - Annals of Applied Mathematics VL - 4 SP - 428 EP - 438 PY - 2022 DA - 2022/06 SN - 33 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/aam/20622.html KW - $\mathbb{Z}_3$-connected, nowhere-zero 3-flow, triangular graphs. AB -

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.

Chuixiang Zhou. (2022). $\mathbb{Z}_3$-Connectivity of 4-Edge-Connected Triangular Graphs. Annals of Applied Mathematics. 33 (4). 428-438. doi:
Copy to clipboard
The citation has been copied to your clipboard