Symmetries and sense of direction in labeled graphs (Q1270775)

The authors consider edge-labeled graphs which model distributed systems. A new characterization of Cayley graphs is provided. This characterization leads to a low polynomial algorithm to test whether a labeled graph is a Cayley graph. No better algorithm is currently known. Other interesting links between symmetries and sense of direction are investigated. The authors show that the class of CG-labeled graphs does not coincide with the class of labeled graphs with sense of direction. The authors also characterize the class of regular labeled graphs with minimal sense of direction, as well as the class of those with group-based sense of direction.