Prove that every unweighted n-vertex graph G and every integer k>=1, there exists a partition of G into at most O(n/k) connected clusters of radius at most k. I dont even have a clue on how to strike this problem. Induction on k??
Partitioning a graph G into at most O(n/k) connected clusters of radius at most k.
2
$\begingroup$
graph-theory
-
0k is not a constant. G(V,E) can be decomposed into clusters in several ways. One way is to decompose it into singleton nodes(here radius is 0 and size of the cluster is 1). Other way is to decompose it into a single cluster (which is the entire graph. Here radius of the cluster is radius of the graph and size of the cluster is 1). – 2012-09-14