Source-Independent path in graph

Question

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?

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

Here an example (created by me):

• Vertex 1: Red/Black/Red
• Vertex 2: Red/Red/Black
• Vertex 3: Red/Red/Black/Green
• Vertex 4: Red/Black/Red/Green

Starting from any vertex as source you using the path above you always reach the destination vertex.

Answer 1

There is the Road Coloring Problem:

The problem: 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.

(link)

It was recently proved (Trahtman 2009) that if the graph is aperiodic and every vertex has the same out-degree, such a coloring exists:

Theorem: Every finite strongly connected aperiodic directed graph of uniform out-degree has a synchronizing coloring.

Trahtman also give an O(n^3) algorithm for the problem.

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).