Redundant networks and minimum distance

Networks in which each node is directly linked to its nearest neighbors exhibit high reliability and message handling capability. The construction of such networks guaranteeing minimal length, for a given degree of redundancy, is formulated in zero-one integer linear programming terms. Initial feasible solutions to the programs are presented, but connectedness is not guaranteed. In the latter case further zero-one integer programs are proposed assuring connectedness, with given initial feasible solutions. The inefficiency of zero-one programs for large networks leads to consideration of alternate redundant connected networks, without guaranteed minimal length. These networks are based on “nearest- neighbor edge sets”, and are simple to construct. Various theorems on the properties of such networks are presented with applications to one-way communicability.