Geodesic
On the Non-(p−1)-Partite Kp-Free Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 9-23.

Voir la notice de l'article provenant de la source Library of Science

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 ∈ E(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?
Keywords: extremal problems, maximal Kp-free graphs, Kp-saturated graphs 
@article{DMGT_2013_33_1_a1,
     author = {Amin, Kinnari and Faudree, Jill and Gould, Ronald J. and Sidorowicz, El\.zbieta},
     title = {On the {Non-(p\ensuremath{-}1)-Partite} {K\protect\textsubscript{p}-Free} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {9--23},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a1/}
}
TY  - JOUR
AU  - Amin, Kinnari
AU  - Faudree, Jill
AU  - Gould, Ronald J.
AU  - Sidorowicz, Elżbieta
TI  - On the Non-(p−1)-Partite Kp-Free Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 9
EP  - 23
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a1/
LA  - en
ID  - DMGT_2013_33_1_a1
ER  - 
%0 Journal Article
%A Amin, Kinnari
%A Faudree, Jill
%A Gould, Ronald J.
%A Sidorowicz, Elżbieta
%T On the Non-(p−1)-Partite Kp-Free Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 9-23
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a1/
%G en
%F DMGT_2013_33_1_a1
Amin, Kinnari; Faudree, Jill; Gould, Ronald J.; Sidorowicz, Elżbieta. On the Non-(p−1)-Partite Kp-Free Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 9-23. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a1/

[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:1h1::AID-JGT1i3.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, (Wadsworth & 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 Rzeszowskiej 118 (1993) 61-66.

[12] P. Turan, An extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452.