Decompositions into Subgraphs of Small Diameter

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 = E0 ∪ E1 ∪ · · · ∪ Ek such that |E0 | n2, and for all 1 i k the diameter of the subgraph spanned by Ei 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 on . This shows that every dense graph can be partitioned into a small number of ‘small worlds’ provided that a 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