Opuscula Math. 35, no. 6 (), 907-914
http://dx.doi.org/10.7494/OpMath.2015.35.6.907
Opuscula Mathematica

# 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.
Keywords: vertex stability, minimal stable graphs, complete $$k$$-partite graphs.
Mathematics Subject Classification: 05C35, 05C60.