On the threshold for k-regular subgraphs of random graphs

Details On the threshold for k-regular subgraphs of random graphs On the threshold for k-regular subgraphs of random graphs

2007-06-08

arxiv.org/abs/0706.1103v1

Mathematics

Combinatorics

Scientific paper

The $k$-core of a graph is the largest subgraph of minimum degree at least $k$. We show that for $k$ sufficiently large, the $(k + 2)$-core of a random graph $\G(n,p)$ asymptotically almost surely has a spanning $k$-regular subgraph. Thus the threshold for the appearance of a $k$-regular subgraph of a random graph is at most the threshold for the $(k+2)$-core. In particular, this pins down the point of appearance of a $k$-regular subgraph in $\G(n,p)$ to a window for $p$ of width roughly $2/n$ for large $n$ and moderately large $k$.

Affiliated with

Also associated with

No associations

Rating

On the threshold for k-regular subgraphs of random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the threshold for k-regular subgraphs of random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the threshold for k-regular subgraphs of random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652362