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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.