Algebraic specification of interconnection network relationships by permutation voltage graph mappings

Symmetries of large networks are used to simplify the specification of a guest-host network relationship. The relevant kinds of symmetries occur not only in Cayley graphs and in group-action graphs, but elsewhere as well. In brief, the critical topological symmetry property of a guest or host is that it is algebraically specifiable as a covering space of a smaller graph. A first objective is to understand the circumstances under which a mapping (a.k.a. “embedding”) between two base graphs can be lifted topologically to a mapping between their respective coverings. A suitable assignment of algebraic elements called “permutation voltages” to a base graph for the intended host network facilitates the construction not only of the intended host, but also of the intended guest and of the intended mapping of the guest into the host. Explicit formulas are derived for measurement of the load, of the congestion, and of the dilation of the lifted mapping. A concluding example suggests how these new formulas open the opportunity to develop optimization methods for algebraically specified guest-host mappings. The first author was partially supported by ONR Contract N00014-85-0768, and the second author was partially supported by NSF Grant CCR-9110824.