Premium
The property of having a k ‐regular subgraph has a sharp threshold
Author(s) -
Letzter Shoham
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20434
Subject(s) - struct , property (philosophy) , combinatorics , random regular graph , induced subgraph isomorphism problem , mathematics , graph , induced subgraph , random graph , core (optical fiber) , discrete mathematics , computer science , line graph , voltage graph , telecommunications , philosophy , epistemology , vertex (graph theory) , programming language , 1 planar graph
In this paper it is proved that in the random graph model G ( n , p ), the property of containing a k ‐regular subgraph, has a sharp threshold for k ≥ 3. It is also shown how to use similar methods to prove, quite easily, the (known fact of) sharpness of having a non empty k ‐core for k ≥ 3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 509–519, 2013