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 ...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 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 i...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.展开更多
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 ...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）.展开更多
Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least A（G） edge-disjoint removable ears, and any brick G distinct from K4 and C6 has at least A（G） - 2 removable e...Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least A（G） edge-disjoint removable ears, and any brick G distinct from K4 and C6 has at least A（G） - 2 removable edges, where A（G） denotes the maximum degree of G. In this paper, we improve the lower bounds for numbers of removable ears and removable edges of 1-extendable graphs. It is proved that any 1-extendable graph G different from K2 and C2n has at least x′（G） edge-disjoint removable ears, and any brick G distinct from Ka and Ce has at least x′（G） - 2 removable edges, where x′（G） denotes the edge-chromatic number of G. Key words 1-extendable graphs, removable ear, removable edge.展开更多
基金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）.
基金Supported by the National Natural Science Foundation of China (Grant No.10831001)the Science-TechnologyFoundation for Young Scientists of Fujian Province (Grant No.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 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.
基金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）
文摘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 National Science Foundation of China under Grant No.10831001the Fujian Provincial Department of Education under Grant No.JA08223
文摘Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least A（G） edge-disjoint removable ears, and any brick G distinct from K4 and C6 has at least A（G） - 2 removable edges, where A（G） denotes the maximum degree of G. In this paper, we improve the lower bounds for numbers of removable ears and removable edges of 1-extendable graphs. It is proved that any 1-extendable graph G different from K2 and C2n has at least x′（G） edge-disjoint removable ears, and any brick G distinct from Ka and Ce has at least x′（G） - 2 removable edges, where x′（G） denotes the edge-chromatic number of G. Key words 1-extendable graphs, removable ear, removable edge.
