2
$\begingroup$

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??

  • 0
    What if $G$ is not connected?2012-09-10
  • 0
    The result should hold recursively..for all the connected components of G.2012-09-10
  • 0
    Is 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
  • 0
    k 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

0 Answers 0