I'm not sure the best way to name this problem, but basically I need to construct a complete $k$-ary tree for $k \geq 2$ which has this nice property as $k=1$ tree that we can create a ring out of it.For example, to construct $k=1$ suppose $N$ is the number of nodes. If for each node $x$ ($\in 0..N-1$), we pick the child as (x+1) % N. Then picking any $r$ as the root, the tree remains the same structure except for there is no connection between $r-1$ and $r$ (modulo $N$). Each node has the same parent or no parent and has the same child or no child for all possible root.For $k>2$ there is no such construct that I can find. Suppose just $k=2$ . If I arrange the binary in which $x$ has two children (x+1) % N and (x+2) % N. It doesn't give a correct tree with all the nodes anymore.Another way is to do (((x-r)%N)*2+1 + r) % N and (((x-r)%N*2+2 + r) % N which gives a correct tree, but seems like there is $N$ possible choice of parent/child depending on root, the structure dramatically different all the times.In other words, given an unknown root $r$, give $x$, it's still possible to know the possible connecting nodes (or bounded the number of connecting nodes < $O(N)$)Another attempt to clarify this question -- an equivalent problem: I need to create a connected graph of out $N$ node, such that when given a node $r$, I can create a complete $k$-ary rooted by $r$ tree by removing some edges out of the graph. Obviously with a complete graph this is possible, can we create a graph in which each node connects to only $O(k)$ other nodes?This works for $k$=1 with a line-graph.
K-ary tree that wrapped around
algorithms;graphs;trees;binary