<p>There is the Road Coloring Problem:</p>

<p><strong>The problem:</strong> <em>Given a directed graph G, colour the edges such that for every vertex, there are a set of instructions that lead to that vertex, from every other vertex.</em></p>

<p>(<a href="http://en.wikipedia.org/wiki/Road_coloring_problem" rel="nofollow">link</a>)</p>

<p>It was recently proved (<a href="http://arxiv.org/abs/0709.0099" rel="nofollow">Trahtman 2009</a>) that if the graph is aperiodic and every vertex has the same out-degree, such a coloring exists:</p>

<p><strong>Theorem:</strong> <em>Every finite <strong>strongly connected aperiodic</strong> directed graph of <strong>uniform out-degree</strong> has a synchronizing coloring.</em></p>

<p>Trahtman also give an O(n^3) algorithm for the problem.</p>

<p>You should search for "road coloring problem algorithm" and its variants (for example one can relax the condition to aperiodicity, but I think it's an open problem so far).</p>
Source-Independent path in graph
<p>Some years ago I read about an algorithm: it labels graph's edges so path from source node X to destination node Y is always the same sequence of labels, independently from which node you select as source X. How is it called?</p>

<p>(I can't remember which kind of conditions should be satisfied by graph)</p>

<p>Here an example (created by me):</p>

<p><img src="https://i.stack.imgur.com/uH6y6.png" alt="Example graph"></p>

<ul>
<li>Vertex 1: Red/Black/Red</li>
<li>Vertex 2: Red/Red/Black</li>
<li>Vertex 3: Red/Red/Black/Green</li>
<li>Vertex 4: Red/Black/Red/Green</li>
</ul>

<p>Starting from any vertex as source you using the path above you always reach the destination vertex. </p>