Symmetries and sense of direction in labeled graphs Original Research Article

We consider edge-labeled graphs which model distributed systems, focus on properties of edge-labelings, and study their impact on graph classes. In particular, we investigate the relation between symmetries, topologies and sense of direction. We study symmetries based on the notion of view and of surrounding, and characterize the corresponding graph classes. Among other results, we show that the completely surrounding symmetric labeled graphs coincides with the class of Cayley graphs with Cayley labelings. We then focus on the relationship between symmetries and sense of direction in regular graphs. We characterize the class of regular labeled graphs with minimal symmetric sense of direction, as well as the class of those with group-based sense of direction.