Conditional connectivity

Abstract

Abstract For a noncomplete graph G , the traditional definition of its connectivity is the minimum number of points whose removal results in a disconnected subgraph with components H 1 ,…, H k . The conditional connectivity of G with respect to some graph‐theoretic property P is the smallest cardinality of a set S of points, if any, such that every component H i of the disconnected graph G ‐ S has property P. A survey of promising properties P is presented. Questions for various P ‐connectivities are listed in analogy with known results on connectivity and line‐connectivity.