On computing a conditional edge-connectivity of a graph

Abstract The conditional edge-connectivity λ ( G : P ) of a graph G ( V , E ) has been defined by Harary as the minimum cardinality | S | of a set S of edges such that G – S is disconnected and every component of G – S has the given graph property P . I n this article we present lower and upper bounds for λ( G : P ) when P is defined as follows: A graph H satisfies property P if it contains more than one vertex. We then present a polynomial-time algorithm for the computation of λ( G : P ). A new generalization of the notion of connectivity is also given.