Graph extension with constant connectivity

In the field of the scaling-up of communication networks, numbers of communication stations (nodes) and the corresponding communication links (edges) are increasing rapidly. The reliability of the networks then becomes important. To keep the reliability of the networks, the connectivity (invulnerability) of the networks should not decrease. In this article, a method of increasing the nodes of a graph with a constant connectivity is proposed, and some examples of graph extension are shown to realize the extended networks. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006