Lower Bounds for Labeling Schemes Supporting Ancestor, Sibling, and Connectivity Queries

Given a tree, a labeling scheme assigns a label, which is a binary string, to each node. Given the labels of any two nodes u  and v, it can be determined, if a certain property holds u for and v, alone from these labels.
For trees of size n, we show that any labeling scheme for testing ancestor relation uses labels of size log n+Ω(loglog n) to the nodes. If the labels has to distinguish the nodes, i.e., the label of a node is unique, we testing for sibling requires labels of size log n+(-)(loglog d)  for trees with degree , and connectivity queries for forests requires labels of size log n+(-)(loglog n) .