Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-02-07T05:07:54.990Z Has data issue: false hasContentIssue false
  • English
  • Français

(k+1)-Cores Have k-Factors

Published online by Cambridge University Press:  11 September 2012

SIU ON CHAN  and
MICHAEL MOLLOY
SIU ON CHAN
Affiliation:
Department of Computer Science, University of Toronto, Ontario, Canada (e-mail: siuon@cs.toronto.edu, molloy@cs.toronto.edu)
MICHAEL MOLLOY
Affiliation:
Department of Computer Science, University of Toronto, Ontario, Canada (e-mail: siuon@cs.toronto.edu, molloy@cs.toronto.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We prove that the threshold for the appearance of a k-regular subgraph in Gn,p is at most the threshold for the appearance of a non-empty (k+1)-core. This improves a result of Pralat, Verstraete and Wormald [5] and proves a conjecture of Bollobás, Kim and Verstraete [3].

Keywords

Primary 05C80
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 6 , November 2012 , pp. 882 - 896
Copyright
Copyright © Cambridge University Press 2012

References

[1]Benjamini, I., Kozma, G. and Wormald, N. (2006) The mixing time of the giant component of a random graph. Preprint, arXiv:math/0610459Google Scholar
[2]Bollobás, B. (2001) Random Graphs, second edition, Cambridge University Press.Google Scholar
[3]Bollobás, B., Kim, J. H. and Verstraete, J. (2006) Regular subgraphs of random graphs. Random Struct. Alg. 29 1–13.Google Scholar
[4]Pittel, B., Spencer, J. and Wormald, N. (1996) Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67 111–151.Google Scholar
[5]Pralat, P., Verstraete, J. and Wormald, N. (2011) On the threshold for k-regular subgraphs of random graphs. Combinatorica 31 565–581.CrossRefGoogle Scholar
[6]Pretti, M. and Weigt, M. (2006) Sudden emergence of q-regular subgraphs in random graphs. Europhys. Lett. 75 8.Google Scholar
[7]Tutte, W. (1952) The factors of graphs. Canad. J. Math. 4 314–328.Google Scholar
[8]West, D. (2001) Introduction to Graph Theory, second edition, Prentice Hall.Google Scholar