Saturated Graphs of Prescribed Minimum Degree. (7th December 2016)
- Record Type:
- Journal Article
- Title:
- Saturated Graphs of Prescribed Minimum Degree. (7th December 2016)
- Main Title:
- Saturated Graphs of Prescribed Minimum Degree
- Authors:
- DAY, A. NICHOLAS
- 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 ).
- Is Part Of:
- Combinatorics, probability and computing. Volume 26:Number 2(2017:Mar.)
- Journal:
- Combinatorics, probability and computing
- Issue:
- Volume 26:Number 2(2017:Mar.)
- Issue Display:
- Volume 26, Issue 2 (2017)
- Year:
- 2017
- Volume:
- 26
- Issue:
- 2
- Issue Sort Value:
- 2017-0026-0002-0000
- Page Start:
- 201
- Page End:
- 207
- Publication Date:
- 2016-12-07
- Subjects:
- 05C35
Combinatorial analysis -- Periodicals
Probabilities -- Periodicals
Computer science -- Mathematics -- Periodicals
511.6 - Journal URLs:
- http://journals.cambridge.org/action/displayJournal?jid=CPC ↗
- DOI:
- 10.1017/S0963548316000377 ↗
- Languages:
- English
- ISSNs:
- 0963-5483
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library STI - ELD Digital Store
- Ingest File:
- 14486.xml