As a result of recent technological developments there is an increasing interest in the interconnection of microcomputers through networks. For general computation the interconnection graphs should have short internode communication paths and should be of low degree, systematically structured, and incrementally extensible. A family of graphs, called multitree structured (MTS) having these properties is presented. The MTS graphs of degree three have the maximum number of nodes, known to date, for given diameters.

A family of regular graphs of degree 3, called Chordal Rings, is presented as a possible candidate for the implementation of a local network of message-connected (micro) computers. For a properly constructed graph in this family having n nodes the diameter, or maximum length message path, is shown to be of 0(n 1/2). The symmetry of the graphs makes it possible to determine message routing by using a simple distributed algorithm. The given algorithm is also potentially useful for the determination of alternate paths in the event of node or link failure.