For a given graph, I want to label all edges with bit strings. These should be the smallest strings possible given the graph, they should all be distinct, and the Hamming distance between two strings should be 1 iff their vertices are connected by an edge.
This means that I want to determine whether $G$ is an induced subgraph of a Hamming graph of bit strings, to find the smallest string length for which this is true, and to actually identify the mapping (which strings go on which vertices).
Are any methods known for doing this, or is anything known about the complexity?
I don't think that this can be done in general:
For two adjacent vertices, one will have to have an even number of $1$s in its label, and the other an odd number of $1$s. But then a triangle (cycle of length $3$) in the graph can't be labelled. (Or any odd cycle for that matter.)