Z3-CONNECTIVITY OF 4-EDGE-CONNECTED TRIANGULAR GRAPHS  

作　　者：Chuixiang Zhou 

机构地区：[1]Center for Discrete Math.,Fuzhou University,Fuzhou 350116,Fujian,PR China

出　　处：《Annals of Applied Mathematics》2017年第4期428-438,共11页应用数学年刊（英文版）

基　　金：supported by JK2015004

摘　　要：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.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.

关 键 词：Z3-connected nowhere-zero 3-flow triangular graphs 

分 类 号：O157.5[理学—数学]