摘要
An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, 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 graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph （k ≥ 4）.
An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, 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 graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph （k ≥ 4）.
基金
Supported by the Science-technology Foundation for Young Scientists of Fujian Province （Grant No. 2007F3070） and National Natural Science Foundation of China （Grant No. 10831001）
