TR-96-14: Symmetries and Sense of Direction in Labeled Graphs

We consider distributed systems modeled by edge-labeled graphs. Properties of the labeling can be used in the design of ecient protocols; for example, sense of direction is known to have a strong impact on the communication complexity of many distributed problems.In this paper, we analyze some relations between topology and symmetries in labeled graphs. In particular, we characterize the classes of completely symmetric and completely surrounding symmetric labeled graphs; we show that the former is a proper subset of the class of regular graphs, while the latter coincides with the class of Cayley graphs.

We then focus on the relationship between symmetries and sense of direction. We show an interesting link between minimal sense of direction in d-regular graphs (i.e., sense of direction that uses d labels) and Cayley graphs. Namely, we prove that a regular graph has a minimal symmetrical sense of direction i it is a Cayley graph. We also discuss the relationship between minimal sense of direction and recently introduced group-based labelings.