An arc colored eulerian multidigraph with l colors is rainbow eulerian if there is an eulerian circuit in which a sequence of l colors repeats.
An old result of Good (see for instance, ) states that a weakly connected multidigraph M has an eulerian circuit if and only if, for every vertex, indegree equals outdegree.
1] is a rainbow eulerian circuit with color sequence ([s.
For instance, the digraph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [GAMMA], where h is the function defined in Figure 1, is a strongly oriented cycle of length 12, since, as Figure 2 shows, we can find a rainbow eulerian circuit with color sequence (dash, line, dots).
n] would thus trace an Eulerian circuit in a directed graph G([A.
As is well known, the necessary and sufficient conditions for the existence of an Eulerian circuit in a graph are that the graph be connected and that the indegrees and outdegrees match at each vertex, making it easy in general to test for the existence of an Eulerian circuit.
Moreover, any deBruijn cycle (obtained from an Eulerian circuit by writing down the new bits in order) can be converted into a universal cycle for [A.
Now we will construct an Eulerian circuit, beginning with the loop-edge.