{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T06:34:25Z","timestamp":1712298865670},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2016,12,7]],"date-time":"2016-12-07T00:00:00Z","timestamp":1481068800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p>A graph <jats:italic>G<\/jats:italic> is <jats:italic>H<\/jats:italic>-saturated if it contains no copy of <jats:italic>H<\/jats:italic> as a subgraph but the addition of any new edge to <jats:italic>G<\/jats:italic> creates a copy of <jats:italic>H<\/jats:italic>. In this paper we are interested in the function sat<jats:italic><jats:sub>t<\/jats:sub><\/jats:italic>(<jats:italic>n,p<\/jats:italic>), defined to be the minimum number of edges that a <jats:italic>K<jats:sub>p<\/jats:sub><\/jats:italic>-saturated graph on <jats:italic>n<\/jats:italic> vertices can have if it has minimum degree at least <jats:italic>t<\/jats:italic>. We prove that sat<jats:italic><jats:sub>t<\/jats:sub><\/jats:italic>(<jats:italic>n,p<\/jats:italic>) = <jats:italic>tn<\/jats:italic> \u2212 <jats:italic>O<\/jats:italic>(1), where the limit is taken as <jats:italic>n<\/jats:italic> tends to infinity. This confirms a conjecture of Bollob\u00e1s when <jats:italic>p<\/jats:italic> = 3. We also present constructions for graphs that give new upper bounds for sat<jats:italic><jats:sub>t<\/jats:sub><\/jats:italic>(<jats:italic>n,p<\/jats:italic>).<\/jats:p>","DOI":"10.1017\/s0963548316000377","type":"journal-article","created":{"date-parts":[[2016,12,7]],"date-time":"2016-12-07T02:51:52Z","timestamp":1481079112000},"page":"201-207","source":"Crossref","is-referenced-by-count":5,"title":["Saturated Graphs of Prescribed Minimum Degree"],"prefix":"10.1017","volume":"26","author":[{"given":"A. NICHOLAS","family":"DAY","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,12,7]]},"reference":[{"key":"S0963548316000377_ref4","doi-asserted-by":"publisher","DOI":"10.2307\/2311408"},{"key":"S0963548316000377_ref12","first-page":"111","article-title":"Results and open problems on minimum saturated graphs.","volume":"72","author":"Pikhurko","year":"2004","journal-title":"Ars Combin."},{"key":"S0963548316000377_ref9","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-072-1"},{"key":"S0963548316000377_ref8","volume-title":"Handbook of Combinatorics","author":"Graham","year":"1995"},{"key":"S0963548316000377_ref13","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/00630343"},{"key":"S0963548316000377_ref6","article-title":"A survey of minimum saturated graphs and hypergraphs","volume":"18","author":"Faudree","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S0963548316000377_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199609)23:1<1::AID-JGT1>3.0.CO;2-O"},{"key":"S0963548316000377_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100109"},{"key":"S0963548316000377_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01904851"},{"key":"S0963548316000377_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/1108023"},{"key":"S0963548316000377_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180103"},{"key":"S0963548316000377_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80035-2"},{"key":"S0963548316000377_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180606"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548316000377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T22:09:36Z","timestamp":1555538976000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548316000377\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,7]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["S0963548316000377"],"URL":"https:\/\/doi.org\/10.1017\/s0963548316000377","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,7]]}}}