Displaying similar documents to “ H -free graphs of large minimum degree.”

On the Non-(p−1)-Partite Kp-Free Graphs

Kinnari Amin, Jill Faudree, Ronald J. Gould, Elżbieta Sidorowicz (2013)

Discussiones Mathematicae Graph Theory

Similarity:

We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?