21
$\begingroup$

Let $T$ be a finite rooted binary tree (where "binary tree" means that each node has at most two children, possibly less) with $n$ nodes in total. Is there a labeling of the nodes of $T$ with the numbers from $0$ to $n-1$, each occurring exactly once, the root having label zero, and so that the label of a vertex is always equal to the label of its parent plus some power of two?

Equivalently:

Let $G$ be the oriented graph whose vertices are the integers between $0$ and $n-1$, with an edge pointing from $i$ to $j$ whenever $j-i$ is a power of two. Is it true that $G$ is "universal" for spanning binary trees, in the sense that every binary tree $T$ on $n$ nodes, oriented away from its root, is a subgraph of $G$?

(This question was asked to me, in slightly different terms, by a bioinformatician friend. At first I didn't believe it because it seems so unreasonable, but experimental data suggests that it might be true, and I have no idea why.)

I emphasize that what makes the question difficult is that the labeling has to be bijective (or, in the second formulation, $T$ is a spanning tree for $G$).

The closest I could find in the literature is the paper "On Universal Graphs for Spanning Trees" by Chung & Graham, J. London Math. Soc. 27 (1983) 203–211, mentioned in an answer to this related question, but I don't see how to apply it or adapt its technique to this particular graph $G$. The only thing I can see is that, at least, $G$ has a sensible number of edges (viz. of the order of $n\log n$).

$\endgroup$
2
  • $\begingroup$ There is a later paper by Bhatt, Chung , Leighton and Rosenberg here (mathweb.ucsd.edu/~fan/mypaps/fanpap/116universal.pdf, 1989) demonstrating a universal graph for spanning binary trees on exactly $n$ vertices with $O(n \log{n})$ edges. [Lemma 1, 2 and Theorem 1]. They rely on a bisector theorem for binary tree - which might be useful. Nevertheless, the conjectured construction seems simpler. $\endgroup$ Oct 17, 2023 at 18:29
  • $\begingroup$ Does the problem become easier if relax the labelling requirement as the difference of labels between parent and child is a positive or negative power of 2? $\endgroup$ Feb 22 at 14:20

2 Answers 2

3
$\begingroup$

I have had a chance to edit my previous answer which was deleted because it was fatally flawed. This argument does not answer the question, but says something about how a minimal counterexample would have to look. I will bring the post back because I think this is a very nice question and perhaps these observations can either be extended to a proof or aid in the search for a counterexample. The first claim is essentially my previously deleted answer. The second claim is along the line of Gerhard Paseman's observations.

If $T$ is a tree on $n$ vertices we will write $|T| = n$. For a rooted binary tree $T$ as in the question let $L$ and $R$ denote the rooted binary trees making up the branches to the left and right of the root node respectively. Assume $T$ is a counter example with $|T|=n$ minimal.

Claim: $|L| \neq |R|$.

Assume $|L| = |R|$. Since $T$ is a minimal counterexample we may give a labeling to $L$ and $R$ satisfying our property. Now multiply all labels of $L$ by $2$ and then add $1$ to all labels. Also multiply all labels of $R$ by $2$ and then add $2$ to all labels. Giving to root node a label of $0$ gives a desired labeling to $T$. Notice scaling by $2$ and shifting preserves the fact that all differences are a power of $2$. Also the root node of $T$ labeled $0$ differs from its children by $1$ and $2$. Because $|L| = |R|$ the labeling will use exactly $\{0,1,\dots, n-1\}$. On $L$ the non-zero odd integers will be used, and the non-zero even integers are used on $R$.

Claim: Neither $|L|$ nor $|R|$ are of the form $2^k - 1$.

WLOG assume $|L| = 2^k - 1$. Since $T$ is a minimal counterexample we may give a labeling to $L$ and $R$ satisfying our property. Now add $1$ to all the labels of $L$ and $2^k$ to all the labels of $R$. Then giving to root node of $T$ the label $0$ satisfies our property, with $L$ labeled with $\{1,2,\dots,2^k - 1\}$ and $R$ labels starting at $2^k$.

$\endgroup$
5
  • 1
    $\begingroup$ I may be misunderstanding something in your reasoning, but if we multiply all labels by a power of 2, we will not have "a labeling of the nodes of T with the numbers from 0 to n−1, each occurring exactly once" any more. $\endgroup$
    – bli
    Jul 4, 2018 at 20:00
  • $\begingroup$ I mean the differences will still all be a power of 2. $\endgroup$ Jul 4, 2018 at 20:02
  • $\begingroup$ Yes, but I think that the fact that you ignore the other property (labels must be from 0 to n) means that the tree with n+1 vertices you construct may have some labels higher than n if the root has 2 children, and those children are the roots of trees with a large enough difference in their numbers of vertices. For instance, if the odd subtree has vertices 1 and 3, and the even subtree has vertices 2, 4 and 6. $\endgroup$
    – bli
    Jul 4, 2018 at 20:12
  • $\begingroup$ I think you missed the crucial condition that the labeling has to be bijective: I'll edit the question to make this more visible. Or perhaps you missed the fact that the binary tree has to be incomplete (your construction does work for the complete binary tree of a certain depth and is, indeed, the most natural way to label it with the constraints in the question). Otherwise, it is I who misunderstood something. $\endgroup$
    – Gro-Tsen
    Jul 4, 2018 at 20:12
  • 1
    $\begingroup$ If the tree is balanced, this might work. Otherwise you end up using labels past n, which goes against the conditions of the question. Gerhard "Always Know Your Arboreal Limits " Paseman, 2018.07.04. $\endgroup$ Jul 4, 2018 at 20:13
0
$\begingroup$

I can get close, but someone else may have to finish it.

John Machacek had some interesting points. Adding the same value to each label preserves the difference property, as does multiplying by a power of two. Also, multiplying by -1 preserves this property, and from this one concludes reversing the order (replacing j by n-j-1) also does.

(Right now, desired means adjacent vertex labels differ by a power of two, that 0 through n-1 is used as in the problem, and not that the root has zero.) Suppose we have the desired labelling for a tree with m nodes and one with n nodes. Suppose further that we can find labelling which assigns 0 to each root. Then we get a desired labelling on n+m+1 vertices by assigning n to the new root, n-1 to the old root of the n tree, n+1 to the m tree, and then modifying the labels of the n and m trees in a predictable fashion. We can do similarly with the new root being labelled with m.

We could complete the proof if we could take this labelling and tweak it so that zero moved to the top. Otherwise we have to find a new way to label the new root, or build such a labelling of the n+m+1 tree so that it can have a root labelled with zero.

Note that 0 can't be transported to any node of a binary tree with such a labelling, as experimenting with n=4 shows.

Gerhard "Thumb Is Not Green Enough" Paseman, 2018.07.04.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.