EXTRACONNECTIVITY OF GRAPHS WITH LARGE GIRTH

Following Harary, the conditional connectivity (edge-connectivity) of a graph with respect to a given graph-theoretic property is the minimum cardinality of a set of vertices (edges), if any, whose deletion disconnects the graph and every remaining component has such a property. We study the case in which all these components are different from a tree whose order is not greater than n. For instance, the recently studied superconnectivity of a maximally connected graph corresponds to this conditional connectivity for n = 1. For other values of n, some sufficient conditions for a graph to have the maximum possible conditional connectivity are given.