Nearly optimal embeddings of trees

Details Nearly optimal embeddings of trees Nearly optimal embeddings of trees

2007-07-13

arxiv.org/abs/0707.2079v1

Mathematics

Combinatorics

Scientific paper

In this paper we show how to find nearly optimal embeddings of large trees in several natural classes of graphs. The size of the tree T can be as large as a constant fraction of the size of the graph G, and the maximum degree of T can be close to the minimum degree of G. For example, we prove that any graph of minimum degree d without 4-cycles contains every tree of size \epsilon d^2 and maximum degree at most (1-2\epsilon)d - 2. As there exist d-regular graphs without 4-cycles of size O(d^2), this result is optimal up to constant factors. We prove similar nearly tight results for graphs of given girth, graphs with no complete bipartite subgraph K_{s,t}, random and certain pseudorandom graphs. These results are obtained using a simple and very natural randomized embedding algorithm, which can be viewed as a "self-avoiding tree-indexed random walk".

Affiliated with

Also associated with

No associations

Rating

Nearly optimal embeddings of 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 Nearly optimal embeddings of trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nearly optimal embeddings of trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-253614