Balanced Graph Partitions

K. D. Protasova


Abstract: We prove that the set of vertices $\mathscr V$, $|\mathscr V|=rk$, of a connected graph $G$ can be split into $r$ subsets of the same cardinality in such a way that the distance between any vertex of $G$ and any subset of the partition is at most $r$.

UDC: 519.1

Received: 29.08.2002
Revised: 24.05.2005

DOI: 10.4213/mzm2681

 English version: Mathematical Notes, 2006, 79:1, 116–121

Bibliographic databases:

• 
• 
• 
• 
•