On the existence of \((k,l)\)-critical graphs (Q1377731): Difference between revisions

Let \(G=(V,E)\) be a graph with connectivity \(\kappa (G)=k\). A set \(X \subseteq V\) with \(|V-X |\geq k+1\) is called a fragment if the number of neighbors of \(X\) in \(V\setminus X\) is \(k\). Let \(W\subseteq V\) be such that \(W\cap X\neq \varnothing\) for each fragment \(X\) of \(G\). Then \(G\) is defined to be locally \((k,l)\)-critical if \(\kappa(G-W')= k-|W'|\) holds for every \(W'\subseteq W\) with \(|W'|<l\). The paper gives a short proof of a recent theorem of Su, stating that every non-complete \(W\)-locally \((k,l)\)-critical graph has \((2l+2)\) distinct ends and \(|W|\geq 2l+2\). This result implies a conjecture of Slater: there exist no \((k,l)\)-critical graphs with \(2l>k\), except \(K_{k+1}\).