Bounds for the Component Order Edge Connectivity

摘要

The component order edge connectivity parameter, λ_c~((k)) (G) or simply λ_c~((k)), is defined as the minimum number of edges that must be deleted from a graph G so that all components of the resulting subgraph have order less than k, where k is a predetermined threshold value. Formulas for λ_c~((k)) have been derived for stars, paths, cycles, and complete graphs; but no formula has been found for an arbitrary graph G. In this work we look at several bounds that can be applied to find the range of possible values for any graph. We then derive from these bounds formulas for λ_c~((k)) of the fan and the wheel.