In this paper we propose a new communication architecture aimed to support and facilitate cooperative behavior and work within colonies of mobile robots. As the number of robots in the group increases, the performance of a broadcasting (one-to-all) based communication system degrades due to the information overflow. Different schemas of local communication (one-to-a few) can be applied instead. We examine a new communication topology for a group of mobile robots inspired by the "small-world" network connectivity. The main advantages of this new type of communication network are: 1. The communication overload that each of the robots would experience if all of them were connected on the same network (1 Ethernet, one-to-all communication) is obviated, 2. The amount of clustering for local teams of robots is high and thus relevant information produced within this team is quickly shared amongst its members, and 3. The characteristic path length is small compared to the case of a regular (lattice-like) network, therefore facilitating the fast diffusion of information across the colony when this is necessary for a global task.