Symmetries in Data Graphs
Arnold L. Rosenberg · SIAM Journal on Computing · 1972
Data graphs were introduced as a vehicle for studying uniformities in the structure of graphs underlying data structures. This paper is devoted to investigating symmetries in data graphs. Such symmetries are of no little significance in every phase of the computational process. They can often be exploited to formulate more efficient algorithms, to simplify the specification of these algorithms, and to facilitate analysis of the resulting programs. The main thrust of this paper is to investigate the influence of various structural features of data graphs on the types of symmetries the data graphs enjoy what features ensure the presence of symmetries of various types, and what features limit the possible types of symmetries. These questions are studied first on the class of all data graphs, and then on the class of addressable (= realizable by relative addressing) data graphs.