On k-leaf connectivity of a random graph |
| |
Authors: | Thomasz Luczak |
| |
Abstract: | We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > 1/4. A threshold function for k-leaf connectivity is also found. |
| |
Keywords: | |
|
|