Year: 2017
Author: Chuixiang Zhou
Annals of Applied Mathematics, Vol. 33 (2017), Iss. 4 : pp. 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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2017-AAM-20622
Annals of Applied Mathematics, Vol. 33 (2017), Iss. 4 : pp. 428–438
Published online: 2017-01
AMS Subject Headings: Global Science Press
Copyright: COPYRIGHT: © Global Science Press
Pages: 11
Keywords: $\mathbb{Z}_3$-connected nowhere-zero 3-flow triangular graphs.