Embedding nearly-spanning bounded degree trees

Details Embedding nearly-spanning bounded degree trees Embedding nearly-spanning bounded degree trees

2007-06-27

arxiv.org/abs/0706.4100v1

Mathematics

Combinatorics

Scientific paper

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d\geq 2 and 0<\epsilon<1, there exists a constant c=c(d,\epsilon) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-\epsilon)n vertices with maximum degree at most d. We also prove that if an (n,D,\lambda)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most \lambda in their absolute values) has large enough spectral gap D/\lambda as a function of d and \epsilon, then G has a copy of every tree T as above.

Affiliated with

Also associated with

No associations

Rating

Embedding nearly-spanning bounded degree trees 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 Embedding nearly-spanning bounded degree trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Embedding nearly-spanning bounded degree trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455870