On vertex stability of complete k-partite graphs

Abstract

Let $H$ be any graph. We say that graph $G$ is $H$-stable if $G-u$ contains a subgraph isomorphic to $H$ for an arbitrary chosen $u\in V(G)$. We characterize all $H$-stable graphs of minimal size where $H$ is any complete $k$-partite graph. Thus, we generalize the results of Dudek and Żak regarding complete bipartite graphs.