Discussiones Mathematicae Graph Theory 33(1) (2013) 9-23
doi: 10.7151/dmgt.1654

Dedicated to the 70th Birthday of Mieczysław Borowiecki

[BIBTex] [PDF] [PS]

On the non-(p-1)-partite Kp-free graphs

Kinnari Amin

Department of Mathematics, Computer Science, and Engineering
Georgia Perimeter College
Clarkston, GA 30021

Jill Faudree

Department of Mathematics and Statistics
University of Alaska Fairbanks
Fairbanks, AK 99775-6660

Ronald J. Gould

Department of Mathematics and Computer Science
Emory University
Atlanta, GA 30322

Elżbieta Sidorowicz

Faculty of Mathematics, Computer Science and Econometrics
University of Zielona Góra
Szafrana 4a, 65--516 Zielona Góra, Poland


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?

Keywords: extremal problems, maximal Kp-free graphs, Kp-saturated graphs

2010 Mathematics Subject Classification: 05C35.


[1]N. Alon, P. Erdös, R. Holzman and M. Krivelevich, On k-saturated graphs with restrictions on the degrees, J. Graph Theory 23(1996) 1--20, doi: 10.1002/(SICI)1097-0118(199609)23:1<1::AID-JGT1>3.0.CO;2-O.
[2]K. Amin, J.R. Faudree and R.J. Gould, The edge spectrum of K4-saturated graphs, J. Combin. Math. Combin. Comp. 81 (2012) 233--242.
[3]C. Barefoot, K. Casey, D. Fisher, K. Fraughnaugh and F. Harary, Size in maximal triangle-free graphs and minimal graphs of diameter 2, Discrete Math. 138 (1995) 93--99, doi: 10.1016/0012-365X(94)00190-T.
[4]G. Chartrand and L. Lesniak, Graphs and Digraphs, Second Edition, (Wads-worth & Brooks/Cole, Monterey, 1986).
[5]P. Erdös, A. Hajnal and J.W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107--1110, doi: 10.2307/2311408.
[6]P. Erdös and R. Holzman, On maximal triangle-free graphs, J. Graph Theory 18 (1994) 585--594.
[7]D.A. Duffus and D. Hanson, Minimal k-saturated and color critical graphs of prescribed minimum degree, J. Graph Theory 10 (1986) 55--67, doi: 10.1002/jgt.3190100109.
[8]Z. Füredi and Á. Seress, Maximal triangle-free graphs with restrictions on the degree, J. Graph Theory 18 (1994) 11--24.
[9]A. Hajnal, A theorem on k-saturated graphs, Canad. J. Math. 17(1965) 720--724, doi: 10.4153/CJM-1965-072-1.
[10]U.S.R. Murty, Extremal nonseparable graphs of diameter two, in: F. Harary ed., Proof Techniques in Graph Theory (Academic Press, New York, 1969) 111--117.
[11]E. Sidorowicz, Size of C3-saturated graphs, Zeszyty Naukowe Politechniki Rzeszows-
kiej 118 (1993) 61--66.
[12]P. Turan, An extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436--452.

Received 3 July 2012
Revised 22 October 2012
Accepted 23 October 2012