We consider edge-labeled graphs which model distributed systems.
Properties of the labeling can be used in the design of efficient protocols;
for example, sense of direction
is known to have a strong impact on the
communication complexity of many distributed problems.
We investigate the relation between
symmetries and topology 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 in
regular graphs.
For these graphs, we show an
interesting link between minimal sense of direction and Cayley graphs.
Namely, we prove that a regular graph has a minimal symmetrical
sense of direction iff it is a Cayley graph.
We also discuss the relationship between minimal
sense of direction and group-based labelings.