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
-
0What if $G$ is not connected? – 2012-09-10
-
0The result should hold recursively..for all the connected components of G. – 2012-09-10
-
0Is k a fixed constant? In this case O(n/k)=O(n), so every vertex can belong to its own cluster. (This is the best possible if $G$ has no edges.) – 2012-09-13
-
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