Decompositions into subgraphs of small diameter

Details Decompositions into subgraphs of small diameter Decompositions into subgraphs of small diameter

2009-06-18

arxiv.org/abs/0906.3530v1

Mathematics

Combinatorics

18 pages

Scientific paper

We investigate decompositions of a graph into a small number of low diameter subgraphs. Let P(n,\epsilon,d) be the smallest k such that every graph G=(V,E) on n vertices has an edge partition E=E_0 \cup E_1 \cup ... \cup E_k such that |E_0| \leq \epsilon n^2 and for all 1 \leq i \leq k the diameter of the subgraph spanned by E_i is at most d. Using Szemer\'edi's regularity lemma, Polcyn and Ruci\'nski showed that P(n,\epsilon,4) is bounded above by a constant depending only \epsilon. This shows that every dense graph can be partitioned into a small number of ``small worlds'' provided that few edges can be ignored. Improving on their result, we determine P(n,\epsilon,d) within an absolute constant factor, showing that P(n,\epsilon,2) = \Theta(n) is unbounded for \epsilon < 1/4, P(n,\epsilon,3) = \Theta(1/\epsilon^2) for \epsilon > n^{-1/2} and P(n,\epsilon,4) = \Theta(1/\epsilon) for \epsilon > n^{-1}. We also prove that if G has large minimum degree, all the edges of G can be covered by a small number of low diameter subgraphs. Finally, we extend some of these results to hypergraphs, improving earlier work of Polcyn, R\"odl, Ruci\'nski, and Szemer\'edi.

Affiliated with

Also associated with

No associations

Rating

Decompositions into subgraphs of small diameter 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 Decompositions into subgraphs of small diameter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decompositions into subgraphs of small diameter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400599