Description
Let f : N
+ → N
+. A family of undirected graphs F has an f-labelling scheme if there is an
adjacency tester A : {0, 1}
+ × {0, 1}
+ → {0, 1} such that, for all graphs G = (V, E) ∈ F with n ≥ 1
vertices, there exists a 1-to-1 labelling function ` : V → {0, 1}
f(n)
such that, for all u, v ∈ V ,
A(`(u), `(v)) =
1 if {u, v} ∈ E
0 if {u, v} 6∈ E.
For example, consider the adjacency tester A : {0, 1}
+ × {0, 1}
+ → {0, 1} where A(x, y) = 1 if
and only x and y are binary strings of the same length that differ in exactly one bit position.
Let Vd be the set of n = 2d vertices in N
d
consisting of the vertices that can be reached from the
origin by moving distance 1 in the positive direction along some subset of the dimensions.
Let Ed be the subsets {u, v} of Vd such that the distance between u and v is exactly 1. Let F be
the family of graphs {Gd = (Vd, Ed) | d ≥ 1}. Then, for the labelling function ` : Vd → {0, 1}
d
that
maps each vertex in Vd to its d coordinates in N
d
, A is an adjacency tester for F.
Here is a picture of G2, with the labels on each node.
01 11 00 10
A labelling scheme is useful for storing a graph in a distributed system, with different parts of
the graph stored in different places. Whenever a processor needs to determine whether two vertices
are adjacent, it can do so by simply applying the adjacency tester to the labels of the two nodes.
1. Prove that the family of all undirected graphs has an f-labelling scheme, where f(n) =
ndlog2 ne.
2. Prove that the family of all undirected trees has an f-labelling scheme, where f(n) =
2dlog2 ne.
3. Prove that if a family of undirected graphs F has an f-labelling scheme, then, for all positive
integers n, there is a graph Gn = (Vn, En) with 2f(n) vertices such that every graph G ∈ F
with n vertices is an induced subgraph of Gn.
4. Let f : N
+ → N
+ be a nondecreasing function. Let G be a family of undirected graphs.
Suppose that, for all positive integers n, there is an unidrected graph Gn = (Vn, En) with
2
f(n) vertices such that every graph G ∈ G with n vertices is an induced subgraph of Gn.
Prove that G has an f
0
-labelling scheme, where f
0
(n) = f(n) + dlog2 ne.
1
