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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom