Removable Edges in a Spanning Tree of a k-connected Graph  

作　　者：Li-qiong XU 

机构地区：[1]School of Sciences,Jimei University

出　　处：《Acta Mathematicae Applicatae Sinica》2013年第4期823-828,共6页应用数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China(No.11171134);the Fujian Province Science Foundation(No.2013J01014,2011J01015,2007F3070)

摘　　要：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 O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding 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 k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.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 O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding 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 k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.

关 键 词：k-connected graph removable edge edge-vertex-cut fragments 

分 类 号：O157.5[理学—数学] TP393.08[理学—基础数学]