Decompositions into subgraphs of small diameter

Abstract

We investigate decompositions of a graph into a small number of low diameter subgraphs. Let P(n,ε,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 ε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édi's regularity lemma, Polcyn and Ruciński showed that P(n,ε,4) is bounded above by a constant depending only ε. 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,ε,d) within an absolute constant factor, showing that P(n,ε,2) = Θ(n) is unbounded for ε< 1/4, P(n,ε,3) = Θ(1/ε^2) for ε> n^{-1/2} and P(n,ε,4) = Θ(1/ε) for ε> 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ödl, Ruciński, and Szemerédi.

18 pages