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

Kinnari Amin; Jill Faudree; Ronald J. Gould; Elżbieta Sidorowicz

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 1, page 9-23
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topKinnari Amin, et al. "On the Non-(p−1)-Partite Kp-Free Graphs." Discussiones Mathematicae Graph Theory 33.1 (2013): 9-23. <http://eudml.org/doc/267782>.

@article{KinnariAmin2013,

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?},

author = {Kinnari Amin, Jill Faudree, Ronald J. Gould, Elżbieta Sidorowicz},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {extremal problems; maximal Kp-free graphs; Kp-saturated graphs; maximal -free graphs; -saturated graphs},

language = {eng},

number = {1},

pages = {9-23},

title = {On the Non-(p−1)-Partite Kp-Free Graphs},

url = {http://eudml.org/doc/267782},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Kinnari Amin

AU - Jill Faudree

AU - Ronald J. Gould

AU - Elżbieta Sidorowicz

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

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 1

SP - 9

EP - 23

AB - 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?

LA - eng

KW - extremal problems; maximal Kp-free graphs; Kp-saturated graphs; maximal -free graphs; -saturated graphs

UR - http://eudml.org/doc/267782

ER -

## References

top- [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] Zbl0857.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. Zbl1252.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] Zbl0821.05031
- [4] G. Chartrand and L. Lesniak, Graphs and Digraphs, Second Edition, (Wadsworth & Brooks/Cole, Monterey, 1986). Zbl0666.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. Zbl0807.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] Zbl0593.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] Zbl0129.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. Zbl0853.05052
- [12] P. Turan, An extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.