I will review some recent work on labellings of the vertex set V of a graph G by subsets of a finite set X. There are many different reasons for and conditions on such labellings. Often, the labelling f is required to be injective; then it is called a set valuation of G.
The power set of X can be viewed as a graph, the hypercube Q, in which subsets are adjacent if they differ by one element, i.e., |S ⊕ T| = 1. (⊕ denotes symmetric difference.) Then f is an injection V(G) → V(Q). The G-distance dG(u,v) can be compared with the Q-distance dQ(f(u),f(v)), and one may require that the ratio of the distances is a constant, k. Then f is called a uniform distance-compatible set labelling of G (in India) or a k-scale embedding of G into Q (in France).
There are a plethora of open problems. In particular, 1-scale hypercube embeddings have been characterized; embeddable graphs are called partial cubes and there is quite a literature. 2-scale embeddings are the next most important case and have not been characterized.
This talk is based on a paper "Uniform distance-compatible set-labelings of graphs" by Prof. Sr. K.A. Germina (to appear in JCISS).