Opuscula Math. 35, no. 6 (2015), 907-914
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.