An adjacency labeling scheme labels the n nodes of a graph with bit strings in a way that allows, given the labels of two nodes, to determine adjacency based only on those bit strings.Though many graph families have been meticulously studied for this problem, a non-trivial labeling scheme for the important family of power-law graphs has yet to be obtained.This family is particularly useful for social and web networks as their underlying graphs are typically modelled as power-law graphs.Using simple strategies and a careful selection of a parameter, we show upper bounds for such labeling schemes of Õ( α √ n) for power law graphs with coefficient α, as well as nearly matching lower bounds.We also show two relaxations that allow for a label of logarithmic size, and extend the upper-bound technique to produce an improved distance labeling scheme for power-law graphs.

A labeling scheme is a method of distributing the information about the structure of a graph among its vertices by assigning short labels, such that a selected function on pairs of vertices can be computed using only their labels. A labeling scheme consists of an encoder that has access to the entire graph and assigns labels to vertices, and a decoder that has access to only the labels of a smaller set of vertices (typically a pair) and returns information about this subset (e.g., whether two vertices are adjacent, or the distance between them in the graph). The main objective is to minimize the maximum label size: the maximum number of bits used in a label of any vertex. Among the applications of labeling schemes are XML search engines, mapping services, and internet routing.