# Coloring edges of a k-ary tree

In simulating a binary branching random walk, I needed to find a proper way to color each walks, so that we could follow a particle for example from its birth time to the end of the simulation, see figure below.

In this model, each node at time $k$ gives birth to a child and continues its own way. The walk is sampled from a (Galton-Watson) tree with proper weight on the edges. Since the number of child here is constant, we have in fact a binary tree $T$.

Let us number the vertices of $T$ as below:

The program generates the walk in the following way. Vertex $1$ is the origin it connects each particle at time $n$ to time $n+1$ and the proper weight. The order of addition from left to right, top to bottom. My coloring convention was as follow: I want the leftmost edges in each of a descendant's to be of the same color than the parent to its ancestor's edge. For example, the path $[1-2-4-8]$ would be the same color, so would $[3-7-14]$. We can easily see that we need $2^n$ (8 in the example) colors to have a walk following this set-up. Suppose we have our colors stored in a vector. Coloring an edges that goes from any vertex to an odd-numbered vertex is easy because you need a new color, but for coloring an edge that goes to an even numbered vertex say $2k$, I found that the proper color was stored at index $f(k)$ in the vector, where $f(k)$ is $$f(k)=\frac{\left(\frac{k}{gcd(k,2^k)}+1\right)}{2}$$

This is sequence A003602 at OEIS.

What I was wondering is if there would be any way to generalize this coloring method to $k$-ary trees. If I'm right, in a ternary tree, we would have to find such a sequence for $0\equiv \mod 3$ labelled vertex. By brute force, the first term of the sequence would be $1,1,2,3,1,4,5,2,6,7$. Any Ideas?

• I don't know how to simply generalize your method, but I would do something different. Take any function $f : [0,1] \to \mathtt{color}$ (e.g. use hue), and make the root $0$ (zero), and any child $\mathtt{parent}+2^{-\mathtt{level}}$. What do you think? Feb 20, 2013 at 22:19

What $k/\gcd(k,2^k)$ does is to divide out any factors of $2$ in $k$; this is what you want because a factor of $2$ corresponds to a leftward step that doesn't change the colour, so this leads you back to the odd-numbered vertex where this colour originated, and then $+1$ and $/2$ yield the colour index.
If you draw out correspondingly numbered $n$-ary trees, you'll find that what generalizes isn't that the number of the left-most vertex is multiplied by $n$, but the number of the second vertex from the right (which is the same thing for $n=2$). Thus, if you're willing to make the penultimate child heir to the ancestral colour, you can calculate the number of the vertex that gave rise to the colour as $k/\gcd(k,n^k)$, and from that you can obtain the colour index as
$$\left\lceil\frac{n-1}n\frac k{\gcd(k,n^k)}\right\rceil\;.$$
• Well, for some reason I had not spot that $m^n$ was the penultimate child in generation $n$ in a $m$-ary tree. Feb 21, 2013 at 2:44