Realizability Results Involving Two Connectivity Parameters

Abstract

There are networks that can be modeled by simple graphs, where edges are perfectly reliable but nodes are subject to failure, e.g. hardwired computer systems. One measure of the “vulnerability” of the network is the connectivity \(\kappa\) of the graph. Another, somewhat related, vulnerability parameter is the component order connectivity \(\kappa_c^{(k)}\), i.e. the smallest number of nodes that must fail in order to ensure that all remaining components have order less than some value \(k\). In this paper we present necessary and sufficient conditions on a 4-tuple \((n,k,a,b)\) for a graph \(G\) to exist having \(n\) nodes, \(\kappa = a\), and \(\kappa_c^{(k)} = b\). Sufficiency of the conditions follows from a specific construction described in our work. Using this construction we obtain ranges of values for the number of edges in a graph having \(n\) nodes, \(\kappa = a\), and \(\kappa_c^{(k)} = b\) thereby obtaining sufficient conditions on the \(5\)-tuple \((n,e,k,a,b)\) for a graph to exist having \(n\) nodes, \(e\) edges, \(\kappa = a\), and \(\kappa_c^{(k)} = b\). In a limited number of special cases, we show the conditions on \((n,e,k,a,b)\) to be necessary as well.