A network is said to have Sense of Direction when the port labeling satisfies a particular set of global consistency constraints. In this paper 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 system. We consider systems whose topology is a regular graph and we study the relationship between structural properties of d-regular graphs and existence of a Sense of Direction which uses exactly d labels (minimal SD). In particular, we identify a property (Cycle Symmetricity) which we show is a necessary condition for minimal SD. Among regular graphs, we then focus on Cayley Graphs and we prove that they always have a minimal Sense of Direction.