Opuscula Math. 35, no. 6 (2015), 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.
- S. Cichacz, A. Görlich, M. Nikodem, A. Żak, Lower bound on the size of \((H;1)\)-vertex stable graphs, Discrete Math 312 (2012) 20, 3026-3029.
- S. Cichacz, A. Görlich, M. Zwonek, A. Żak, On \((C_n,k)\) stable graphs, Electron. J. Comb. 18 (2011) 1, #P205.
- R. Diestel, Graph Theory, 2nd ed., Springer-Verlag, 2000.
- A. Dudek, A. Szymański, M. Zwonek, \((H,k)\) stable graphs with minimum size, Discuss. Math. Graph Theory 28 (2008), 137-149.
- A. Dudek, M. Zwonek, \((H,k)\) stable bipartite graphs with minimum size, Discuss. Math. Graph Theory 29 (2009), 573-581.
- A. Dudek, A. Żak, On vertex stability with regard to complete bipartite subgraphs, Discuss. Math. Graph Theory 30 (2010), 663-669.
- J.-L. Fouquet, H. Thuillier, J-M. Vanherpe, A.P. Wojda, On \((K_q; k)\) vertex stable graphs with minimum size, Discrete Math. 312 (2012) 14, 2109-2118.
- J.-L. Fouquet, H. Thuillier, J-M. Vanherpe, A.P. Wojda, On \((K_q; k)\) vertex stable graphs with small \(k\), Electron. J. Comb. 19 (2012) 2, #P50.
- A. Żak, On \((K_q;k)\)-stable graphs, J. Graph Theory 74 (2013) 2, 216-221.
- A. Żak, General lower bound on the size of \((H;k)\)-stable graphs, J. Comb. Optim. 29 (2015), 367-372.
- Mateusz Nikodem
- AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Krakow, Poland
- Communicated by Mirko Horňák.
- Received: 2013-12-10.
- Revised: 2015-01-19.
- Accepted: 2015-03-16.
- Published online: 2015-06-06.
