High connectivity keeping sets in \(n\)-connected graphs (Q705749): Difference between revisions

This paper is a contribution to the theory of graph connectivity. The main theorem is that, for each positive integer \(k\), if \(G\) is a graph with vertex-connectivity \(\kappa(G)= n\) which is of sufficiently large order \(h_{n}(k)\), then there is a set \(W\) of \(k\) vertices such that \(G\backslash W\) is \((n-2)\)-connected. (\(G\) itself need not be finite.) Examples are given to show that we cannot replace \(n-2\) with \(n-1\). It is further shown that we cannot insist that there is such a set \(W\) whose vertices induce a connected subgraph of \(G\). The function \(h_{n}(k)\) given by the method of proof grows rapidly with \(k\), but the author suggests that one can do better, and that it may even be the case that it can be taken to be linear in \(k\). The core of the proof is to show that every finite graph \(G\) which is \(n\)-minimal (i.e. \(\kappa(G)=n\) but \(\kappa(G\backslash e)\neq n\) for all \(e\in E(G)\)) contains an independent set \(W\) of vertices, each of degree \(n\) in \(G\), with \(| W|=k+1\) and \(\kappa(G\backslash W)\geq n-2\). The proof uses facts about fragments of \(G\) (i.e. unions of vertex sets of some components of \(G\backslash T\) where \(T\) is a separating set of order \(\kappa(G)\)) and atoms (i.e. fragments of smallest vertex number), together with an argument establishing that, for \(m\geq 2\in \mathbb N\), there is a set \(W\) of vertices any two of which are far apart from each other, in the sense that any path between them, all of whose interior vertices have degree at most \(m\), must be long. The attempt to replace an independent set \(W\) with a connected one leads to the notion of \((n,k)_{c}\)-graphs, those for which \(\kappa(G\backslash W)=n-| W|\) for all \(W\subseteq V(G)\) with \(| W|\leq k\). The author proves several properties of \((n,k)_{c}\)-graphs: for example, that every \((n,7)_{c}\)-graph has at most \(4n^{4}\) vertices (so is finite) and has diameter \(\leq 4\), or that an \((n,k)_{c}\)-graph with \(k\geq 3\) and \(k>n/2\) is isomorphic to \(K_{n+1}\). Some conjectures are also made.