**Problem of the Week**

**Math Club**

**BUGCAT 2020**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

seminars:comb:abstract.201302zas

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_{G}(u,v) can be compared with the Q-distance d_{Q}(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).

seminars/comb/abstract.201302zas.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported