Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-06T22:48:18.760Z Has data issue: false hasContentIssue false
  • English
  • Français

Saturated Graphs of Prescribed Minimum Degree

Published online by Cambridge University Press:  07 December 2016

A. NICHOLAS DAY
A. NICHOLAS DAY*
Affiliation:
School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, UK (e-mail: a.n.day@qmul.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A graph G is H-saturated if it contains no copy of H as a subgraph but the addition of any new edge to G creates a copy of H. In this paper we are interested in the function satt(n,p), defined to be the minimum number of edges that a Kp-saturated graph on n vertices can have if it has minimum degree at least t. We prove that satt(n,p) = tn − O(1), where the limit is taken as n tends to infinity. This confirms a conjecture of Bollobás when p = 3. We also present constructions for graphs that give new upper bounds for satt(n,p).

Keywords

05C35
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 2 , March 2017 , pp. 201 - 207
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Alon, N., Erdős, P., Holzman, R. and Krivelevich, M. (1996) On k-saturated graphs with restrictions on the degrees. J. Graph Theory 23 1–20.Google Scholar
[2] Bollobás, B. (1965) On generalized graphs. Acta Math. Acad. Sci. Hungar. 16 447–452.CrossRefGoogle Scholar
[3] Duffus, D. A. and Hanson, D. (1986) Minimal k-saturated and color critical graphs of prescribed minimum degree. J. Graph Theory 10 55–67.CrossRefGoogle Scholar
[4] Erdős, P., Hajnal, A. and Moon, J. W. (1964) A problem in graph theory. Amer. Math. Monthly 71 1107–1110.Google Scholar
[5] Erdős, P. and Holzman, R. (1994) On maximal triangle-free graphs. J. Graph Theory 18 585–594.Google Scholar
[6] Faudree, J., Faudree, R. and Schmitt, J. (2011) A survey of minimum saturated graphs and hypergraphs. Electron. J. Combin. 18 DS19.Google Scholar
[7] Füredi, Z. and Seress, Á. (1994) Maximal triangle-free graphs with restrictions on the degrees. J. Graph Theory 18 11–24.CrossRefGoogle Scholar
[8] Graham, R. L., Grötschel, M. and Lovász, L., eds (1995) Handbook of Combinatorics, Vol. 2, Elsevier.Google Scholar
[9] Hajnal, A. (1965) A theorem on k-saturated graphs. Canad. J. Math. 17 720–724.Google Scholar
[10] Lubell, D. (1966) A short proof of Sperner's theorem. J. Combin. Theory 1 299.Google Scholar
[11] Meshalkin, L. D. (1963) A generalization of Sperner's theorem on the number of subsets of a finite set. Theor. Probab. Appl. 8 203–204.CrossRefGoogle Scholar
[12] Pikhurko, O. (2004) Results and open problems on minimum saturated graphs. Ars Combin. 72 111–127.Google Scholar
[13] Yamamoto, K. (1954) Logarithmic order of free distributive lattices. J. Math. Soc. Japan 6 343–353.Google Scholar