PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 1 | 9-23
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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?
Wydawca
Rocznik
Tom
33
Numer
1
Strony
9-23
Opis fizyczny
Daty
wydano
2013-03-01
online
2013-04-13
Twórcy
autor
  • Department of Mathematics, Computer Science, and Engineering Georgia Perimeter College Clarkston, GA 30021, kinnari.v.amin@gmail.com
autor
  • Department of Mathematics and Statistics University of Alaska Fairbanks Fairbanks, AK 99775-6660, ffjrf@uaf.edu
  • Department of Mathematics and Computer Science Emory University Atlanta, GA 30322, rg@mathcs.emory.edu
  • Faculty of Mathematics, Computer Science and Econometrics University of Zielona Góra Szafrana 4a, 65–516 Zielona Góra, Poland, e.sidorowicz@wmie.uz.zgora.pl
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1654
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.