Discussiones Mathematicae Graph Theory 33(1) (2013)
9-23
DOI: https://doi.org/10.7151/dmgt.1654
Dedicated to the 70th Birthday of Mieczysław Borowiecki
On the non-(p-1)-partite Kp-free graphs
Kinnari Amin
Department of Mathematics, Computer Science, and Engineering | Jill Faudree
Department of Mathematics and Statistics | Ronald J. Gould
Department of Mathematics and Computer Science | Elżbieta Sidorowicz
Faculty of Mathematics, Computer Science and Econometrics |
Abstract
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.
References
[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
Close