DC Field | Value | Language |
---|---|---|
dc.contributor.author | Condon, Padraig | ko |
dc.contributor.author | Diaz, Alberto Espuny | ko |
dc.contributor.author | Kuhn, Daniela | ko |
dc.contributor.author | Osthus, Deryk | ko |
dc.contributor.author | Kim, Jaehoon | ko |
dc.date.accessioned | 2020-01-29T03:20:10Z | - |
dc.date.available | 2020-01-29T03:20:10Z | - |
dc.date.created | 2020-01-29 | - |
dc.date.created | 2020-01-29 | - |
dc.date.created | 2020-01-29 | - |
dc.date.created | 2020-01-29 | - |
dc.date.created | 2020-01-29 | - |
dc.date.created | 2020-01-29 | - |
dc.date.issued | 2019-12 | - |
dc.identifier.citation | ELECTRONIC JOURNAL OF COMBINATORICS, v.26, no.4, pp.1 - 22 | - |
dc.identifier.issn | 1077-8926 | - |
dc.identifier.uri | http://hdl.handle.net/10203/271829 | - |
dc.description.abstract | Posa's theorem states that any graph G whose degree sequence d(1) <= . . . <= d(n) satisfies d(i) >= i + 1 for all i < n/2 has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs G of random graphs, i.e. we prove a 'resilience version' of Posa's theorem: if pn >= C log n and the i-th vertex degree (ordered increasingly) of G subset of G(n,p) is at least (i + o(n))p for all i < n/2, then G has a Hamilton cycle. This is essentially best possible and strengthens a resilience version of Dirac's theorem obtained by Lee and Sudakov. Chvatal's theorem generalises Posa's theorem and characterises all degree sequences which ensure the existence of a Hamilton cycle. We show that a natural guess for a resilience version of Chvatal's theorem fails to be true. We formulate a conjecture which would repair this guess, and show that the corresponding degree conditions ensure the existence of a perfect matching in any subgraph of G(n,p) which satisfies these conditions. This provides an asymptotic characterisation of all degree sequences which resiliently guarantee the existence of a perfect matching. | - |
dc.language | English | - |
dc.publisher | ELECTRONIC JOURNAL OF COMBINATORICS | - |
dc.title | Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs | - |
dc.type | Article | - |
dc.identifier.wosid | 000506406500001 | - |
dc.identifier.scopusid | 2-s2.0-85078122070 | - |
dc.type.rims | ART | - |
dc.citation.volume | 26 | - |
dc.citation.issue | 4 | - |
dc.citation.beginningpage | 1 | - |
dc.citation.endingpage | 22 | - |
dc.citation.publicationname | ELECTRONIC JOURNAL OF COMBINATORICS | - |
dc.identifier.doi | 10.37236/8279 | - |
dc.contributor.localauthor | Kim, Jaehoon | - |
dc.contributor.nonIdAuthor | Condon, Padraig | - |
dc.contributor.nonIdAuthor | Diaz, Alberto Espuny | - |
dc.contributor.nonIdAuthor | Kuhn, Daniela | - |
dc.contributor.nonIdAuthor | Osthus, Deryk | - |
dc.description.isOpenAccess | Y | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | LOCAL RESILIENCE | - |
dc.subject.keywordPlus | THEOREM | - |
dc.subject.keywordPlus | EXISTENCE | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.