MINIMAL SENSE OF DIRECTION IN REGULAR NETWORKS

A network is said to have Sense of Direction when the port labeling sa tisfies a particular set of global consistency constraints. In this pa per we study the link between the topology of a system and the number of labels that are necessary to have a Sense of Direction in that syst em. We consider systems whose topology is a regular graph and we study the relationship between structural properties of d-regular graphs an d existence of a Sense of Direction which uses exactly d labels (minim al SD). In particular, we identify a property (cycle symmetricity) whi ch we show is a necessary condition for minimal SD. Among regular grap hs, we then focus on Cayley graphs and we prove that they always have a minimal Sense of Direction. (C) 1997 Published by Elsevier Science B .V.