Component Order Edge Connectivity For Graphs Of Fixed Size and Order

Abstract

Given a graph \(G := (V, E)\) and an integer \(k \geq 2\), the \({component \;order\; edge connectivity}\) of \(G\) is the smallest size of an edge set \(D\) such that the subgraph induced by \(G – D\) has all components of order less than \(k\). Let \({G}(n,m)\) denote the collection of simple graphs \(G\) with \(n\) vertices and \(m\) edges. In this paper, we investigate properties of component order edge connectivity for \({G}(n,m)\), particularly proving results on the maximum and minimum values of this connectivity measure for \({G}(n,m)\) specific values of \(n\), \(m\), and \(k\).