×

On the non-\((p-1)\)-partite \(K_p\)-free graphs. (English) Zbl 1291.05095

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\)?

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI