On Component Order Edge Connectivity Of a Complete Bipartite Graph

Abstract

The traditional parameter used as a measure of vulnerability of a network modeled by a graph with perfect nodes and edges that may fail is edge connectivity \(\lambda\). For the complete bipartite graph \(K_{p,q}\), where \(1 \leq p \leq q\), \(\lambda(K_{p,q}) = p\). In this case, failure of the network means that the surviving subgraph becomes disconnected upon the failure of individual edges. If, instead, failure of the network is defined to mean that the surviving subgraph has no component of order greater than or equal to some preassigned number \(k\), then the associated vulnerability parameter, the component order edge connectivity \(\lambda_c^{(k)}\), is the minimum number of edges required to fail so that the surviving subgraph is in a failure state. We determine the value of \(\lambda_c^{(k)}(K_{p,q})\) for arbitrary \(1 \leq p \leq q\) and \(4 \leq k \leq p+q\). As it happens, the situation is relatively simple when \(p\) is small and more involved when \(p\) is large.