====== Thomas Zaslavsky (Binghamton) ======

====== Hypercubical Set Labellings of Graphs ======

===== Abstract for the Combinatorics Seminar 2013 February 5 =====

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 d<sub>G</sub>(u,v) can be compared with the Q-distance d<sub>Q</sub>(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).


----