Lately I've been looking into graphs (simple, undirected, finite) that are in some way weak when it comes to connectivity, that is:

Let $G$ be a graph of order $n$. We'll say that $G$ is $k$-weak if for every induced connected subgraph $H$ of order $k$, $G \setminus H$ is disconnected.

I wish to find a good (or any) characterization of such graphs. It is fairly easy to show that trees are $2$-weak iff. every leaf is a neighbour of a vertex of a degree greater than $2$, and the condition is necessary for all graphs, but it isn't sufficient in general. However, I haven't been able to find any publications on the topic, even for $k=2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.