k连通图在边点割原子与点割上的可去边

Removable Edges in an Edge-vertex Cut Atom of a k-connected Graph

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出某些k连通图中在特定子图上可去边的分布情况,得到了最小度至少为(3(k-1)/2)或围长至少为4的k连通图(k≥4)中由边点割原子与点割所导出的子图的每一条边都是可去边.

Contracible edges and removable edges in connected graphs are a powerful tool to study the structures of graphs and to prove some properties of connected graphs by induction.In this paper by ananlyzing the properties of edge-vertex cut fragment we show that in a k-connected graph G with minimum degree at least δ（G）≥（3（k-1）/2） or girth at least 4,every edges of graph induced by edge-vertex cut atom and vertex cut are removable.