Components and graph automorphisms of standard 2 × 2-switch banyan networks

The standard networks of this paper are the Omega network of Lawrie and its various equivalent counterparts and another network which corresponds to the inverse CC-banyan (or restricted data manipulator) but is also built from 2 × 2-crossbar switches. We present several characterizations of graphs which determine the linkage of the switches in these networks. For the graph of the Omega network, such a characterization has been given by Kruskal and Snir and by Bermond, Fourneau, and Jean-Marie. Some of the results of this paper are variants of or inspired by the findings of the latter authors. Apart from the banyan property and conditions on the components of certain subgraphs, use is made of variations of the familiar buddy property. The automorphisms of the aforementioned graphs are determined as well. The structure of the standard networks appears to be largely determined by these mappings.