On the Non-(p−1)-Partite Kp-Free Graphs
Kinnari Amin ; Jill Faudree ; Ronald J. Gould ; Elżbieta Sidorowicz
Discussiones Mathematicae Graph Theory, Tome 33 (2013), p. 9-23 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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?

Publié le : 2013-01-01
EUDML-ID : urn:eudml:doc:267782 
@article{bwmeta1.element.doi-10_7151_dmgt_1654,
     author = {Kinnari Amin and Jill Faudree and Ronald J. Gould and El\.zbieta Sidorowicz},
     title = {On the Non-(p-1)-Partite Kp-Free Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {33},
     year = {2013},
     pages = {9-23},
     zbl = {1291.05095},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1654}
}

Kinnari Amin; Jill Faudree; Ronald J. Gould; Elżbieta Sidorowicz. On the Non-(p−1)-Partite Kp-Free Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 9-23. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1654/

[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[Crossref] | Zbl 0857.05051

[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. | Zbl 1252.05184

[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[Crossref] | Zbl 0821.05031

[4] G. Chartrand and L. Lesniak, Graphs and Digraphs, Second Edition, (Wadsworth & Brooks/Cole, Monterey, 1986). | Zbl 0666.05001

[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[Crossref]

[6] P. Erdős and R. Holzman, On maximal triangle-free graphs, J. Graph Theory 18 (1994) 585-594. | Zbl 0807.05040

[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[Crossref] | Zbl 0593.05040

[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[Crossref] | Zbl 0129.39901

[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. | Zbl 0853.05052

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