Description

The basic problem is very simple – to raise. Take the k dimensional nonzero 0-1 vectors. What graphs can be labeled with them without repeated labels so that every ledge is labeled with the mod 2 sum of its endvertices. So the number of vertices plus the number of edges is at most 2^k-1. The particularly interesting case when it is exactly 2^k-1. The problem is solved for paths of 2^k-1 vertices. But it is surprisingly difficult and open for trees too. There are some recent results, e.g., for caterpillars.

Several relaxations are open, though most of them seem to be very difficult. What happens if we have fewer vertices and edges? What if just the edges must get different labels?

There are several other versions to raise too, this is an interesting research area as well, but the main goal is to get some new results about trees.

Example Conjecture: All trees with only odd-degree vertices and with 2^k vertices have such a labeling.