Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 81
  • Download : 5
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.
Publisher
ELECTRONIC JOURNAL OF COMBINATORICS
Issue Date
2019-12
Language
English
Article Type
Article
Citation

ELECTRONIC JOURNAL OF COMBINATORICS, v.26, no.4

ISSN
1077-8926
DOI
10.37236/8279
URI
http://hdl.handle.net/10203/271829
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
8279-PDF file-30352-1-10-20191212.pdf(344.23 kB)Download

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0