Thursday, September 6, 2007

Graph labellings and coding theory

So, here's what I did today (among, of course, other stuff):

Call a graph G (n,k)Hamming-representable if there is a labeling f: V(G) -> (F_2)^n such that two vertices v, w are adjacent iff the Hamming distance between f(v) and f(w) is at most k. If G is (n,k)Hamming-representable for some choice of n and k, we'll just call it Hamming-representable.

In addition, say that G is (n,k)Hamming-regular when two vertices are adjacent iff the Hamming distance between their labels is k. Same deal with just "Hamming-regular."

So it's not hard to show that all trees on n edges are (n,1)Hamming-regular; root the tree, assign each vertex apart from the root a number from 1 to n, assign the root the label (0,0,0,...,0), and assign a vertex v a label which has a 1 in the mth spot iff the path from the root to v passes through the vertex assigned m. (If you don't follow that, comment me; I'll attempt to make a diagram so it'll hopefully be clearer.)

Some conjectures/questions:

1. Are all Hamming-regular graphs also Hamming-representable? Trees are (duh), but what about others?

2. Are all graphs Hamming-representable? (Obviously, this is a stronger statement in the affirmative than #1...)

(Edit: So, a thought. Assign an index i to each vertex; set the "bit" in the ith place to 1 if the vertex you're labelling is either vertex i or adjacent to i. Does this work? I'm too tired to prove/find a counterexample; any takers?

Edit^2: Grr, doesn't work. Certain trees, for example. So it's trickier than I thought.)

3. What's the growth rate for the maxmin of n for all Hamming-representable graphs of the same size? Can we construct an (n,k)Hamming-labelling of a tree where n is logarithmic in the number of vertices, or is our current construction optimal?

I think I had more. But I don't remember them. Yeah.

As always, any thoughts/comments/opinions are greatly valued. Comment, people!

No comments: