Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E（G）, define d（e） = d（u） ＋ d（v）. Let F denote the set of all simple 2-edge-connected graphs on n ） 4 vertices such that G∈ F if ...Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E（G）, define d（e） = d（u） ＋ d（v）. Let F denote the set of all simple 2-edge-connected graphs on n ） 4 vertices such that G∈ F if and only if d（e） ＋ d（e′） ≥ 2n for every pair of independent edges e, e′ of G. We prove in this paper that for each G ∈ F, G is not Z3-connected if and only if G is one of K2,n-2, K3,n-3, K^＋2,n-2,K^＋ 3,n-3 or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 20]0, 310： 3390-3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308： 6233-6240].展开更多
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 sequen...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 T1T2%…Tk in G such that for 1 〈 i 〈 k - 1, IE（Ti）∩E（Ti＋1）1= 1 and E（Ti） n E（Tj）=φ if j 〉 i＋1. Two edges e, e＇∈ E（G） are triangularly connected if there is a triangle-path T1, T2,... , Tk in G such that e ∈ E（T1） and er ∈ E（Tk）. 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 Z3-connected, unless it has a triangularly connected component which is not Z3-connected but admits a nowhere-zero 3-flow.展开更多
基金Acknowledgements The first author was supported by the Excellent Doctorial Dissertation Cultivation Grant from Huazhong Normal University （2013YBYB42）. The second author was supported in part by the National Natural Science Foundation of China （Grant No. 11171129） and the Doctoral Fund of Ministry of Education of China （Grant No. 20130144110001）.
文摘Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E（G）, define d（e） = d（u） ＋ d（v）. Let F denote the set of all simple 2-edge-connected graphs on n ） 4 vertices such that G∈ F if and only if d（e） ＋ d（e′） ≥ 2n for every pair of independent edges e, e′ of G. We prove in this paper that for each G ∈ F, G is not Z3-connected if and only if G is one of K2,n-2, K3,n-3, K^＋2,n-2,K^＋ 3,n-3 or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 20]0, 310： 3390-3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308： 6233-6240].
文摘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 T1T2%…Tk in G such that for 1 〈 i 〈 k - 1, IE（Ti）∩E（Ti＋1）1= 1 and E（Ti） n E（Tj）=φ if j 〉 i＋1. Two edges e, e＇∈ E（G） are triangularly connected if there is a triangle-path T1, T2,... , Tk in G such that e ∈ E（T1） and er ∈ E（Tk）. 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 Z3-connected, unless it has a triangularly connected component which is not Z3-connected but admits a nowhere-zero 3-flow.
