Saturated Graphs of Prescribed Minimum Degree. (7th December 2016)

• Record Type: Journal Article
• Authors: DAY, A. NICHOLAS
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 2(2017:Mar.)
• Page Start: 201
• Page End: 207
• Publication Date: 2016-12-07
• Subjects: 05C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000377
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : 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 sat t ( 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 sat t ( 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 sat t ( n, p ).