Generalizaions of critical connectivity of graphs (Q1115453)

Let \(\mu\) (G) denote the connectivity of a graph G. If T is a vertex separating set of G with \(| T| =\mu (G)\), then T is called a smallest separating set of G. Let \({\mathfrak T}(G)\) be the collection of all subgraphs of G induced by the smallest separating sets of G. For \(T\in {\mathfrak T}(G)\), a T-fragment is a union of at least one, but not all components of G-T. A subgraph F of G that is a T-fragment for some \(T\in {\mathfrak T}(G)\) is called a fragment of G. For a graph G, let \({\mathfrak S}\) be a non-empty set of subsets of V(G) and define \({\mathfrak T}_{{\mathfrak S}}(G)=\{T\in {\mathfrak T}(G)|\) there is an \(S\in {\mathfrak S}\) with \(S\subseteq T\}\). An \({\mathfrak S}\)-fragment of G is a T-fragment of G for some \(T\in {\mathfrak T}_{{\mathfrak S}}(G)\). An \({\mathfrak S}\)-fragment of G that does not properly contain another \({\mathfrak S}\)-fragment is called an \({\mathfrak S}\)-end of G while one with the smallest number of vertices is called an \({\mathfrak S}\)-atom. The order of an \({\mathfrak S}\)-atom is denoted by \(a_{{\mathfrak S}}(G)\). The graph G is called \({\mathfrak S}\)-critical if and only if every \(S\in {\mathfrak S}\) is contained in some \(T\in {\mathfrak T}(G)\) and for every \({\mathfrak S}\)-fragment F, there is a \(T\in {\mathfrak T}(G)\) such that \(T\cap F\neq \emptyset\) and \(T\cap (F\cup T_ F)\) contains some \(S\in {\mathfrak S}\) (where \(T_ F\) is the unique element of \({\mathfrak T}(G)\) that determines the fragment F). It is shown that if A is an \({\mathfrak S}\)-atom of G for which there exists a \(T\in {\mathfrak T}(G)\) with \(T\cap A=\emptyset\) and such that \(T\cap (A\cup T_ A)\) contains \(S\in {\mathfrak S}\), then \(A\subseteq T\) and \(| A| \leq | T-T_ A|\). As a consequence it is deduced that for every \({\mathfrak S}\)- critical graph G, \(a_{{\mathfrak S}}(G)\leq \mu (G)\) holds and that every \({\mathfrak S}\)-critical graph is 2-connected. For \(T\subseteq V(G)\) let \(N(T;G)=\cup \{\{x,y\}-T| xy\in E(G)\wedge \{x,y\}\cap T\neq \emptyset \}\). The author shows that if A is an \({\mathfrak S}\)-atom of an \({\mathfrak S}\)- critical graph G, then there is an \({\mathfrak S}\)-fragment F disjoint from A and an \(R\subseteq V(F)\) with \(| R| \leq \mu (G)\) such that there is no \(S\in {\mathfrak S}\) in \(F\cup N(F-R;G)\) with \(S\cap (F-R)\neq \emptyset\). The author then considers some applications of these results. It is shown that every contraction-critical finite graph G has at least \(| V(G)| /3\) triangles and that a finite graph G is 8-connected if every complete subgraph of G is contained in a smallest separating set of G. Some additional classes of graphs (namely, almost critical graphs, and \(C_ k\)-critical graphs) as well as some of their applications are studied.