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

• Autorzy: Kinnari Amin , Jill Faudree , Ronald J. Gould , Elżbieta Sidorowicz
• Języki publikacji: EN

Abstrakty

EN

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?

Słowa kluczowe

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 1
• Strony: 9-23

Daty

wydano

2013-03-01

online

2013-04-13

Twórcy

autor

Kinnari Amin

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

autor

Jill Faudree

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

autor

Ronald J. Gould

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

autor

Elżbieta Sidorowicz

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1654