Amin, Kinnari; Faudree, Jill; Gould, Ronald J.; Sidorowicz, Elżbieta On the non-\((p-1)\)-partite \(K_p\)-free graphs. (English) Zbl 1291.05095 Discuss. Math., Graph Theory 33, No. 1, 9-23 (2013). Summary: We say that a graph \(G\) is maximal \(K_p\)-free if \(G\) does not contain \(K_p\) but if we add any new edge \(e \in E(\overline G)\) to \(G\), then the graph \(G + e\) contains \(K_p\). We study the minimum and maximum size of non-\((p-1)\)-partite maximal \(K_p\)-free graphs with \(n\) vertices. We also answer the interpolation question: for which values of \(n\) and \(m\) are there any \(n\)-vertex maximal \(K_p\)-free graphs of size \(m\)? Cited in 17 Documents MSC: 05C35 Extremal problems in graph theory Keywords:extremal problems; maximal \(K_p\)-free graphs; \(K_p\)-saturated graphs PDFBibTeX XMLCite \textit{K. Amin} et al., Discuss. Math., Graph Theory 33, No. 1, 9--23 (2013; Zbl 1291.05095) Full Text: DOI