Removable Edges in a 5-Connected Graph

作     者：Li Qiong XU Xiao Feng GUO 

作者机构：School of Sciences Jimei University Fujian 361023 P. R. China School of Mathematics Sciences Xiamen University Fujian 361005 P. R. China 

出 版 物：《Journal of Mathematical Research and Exposition》 (数学研究与评论（英文版）)

年 卷 期：2011年第31卷第4期

页      面：617-626页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Supported by the National Natural Science Foundation of China (Grant No.10831001) the Science-TechnologyFoundation for Young Scientists of Fujian Province (Grant No.2007F3070) 

主　　题：5-connected graph removable edge edge-vertex-atom. 

摘      要：An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.