What type of Hamming Graph is this?

I have a set of unique strings (with an alphabet size of >=4) of equal length to represent the vertices (not all possible strings are represented in the graph). I have an edge between a pair of vertices if the Hamming distance between the two strings is 1.

I have an interest in graphs and how they can be use in my biological research. So I've been trying to find out the name of this type of graph so I can try to understand more about it and how such graphs can be constructed and analysed efficiently for graphs with a large number of vertices (in the order of 100's of thousands to millions). However, I have no formal training in Maths so I'm finding it difficult to understand the formal language often used to describe graphs.

So far I've seen mention of Hamming Graph, Complete Hamming Graph, Partial Hamming Graphs and others. Your guidance would be most invaluable!

• Hm, similar graphs occur in set theory in the context of “$\mathcal{G}_0$ dichotomy”. But the set-theoretic literature will probably not help and even if the notation is used elsewhere you probably cannot use the web search to look for “$\mathcal{G}_0$”. Commented Jun 27, 2013 at 22:52
• I do not understand what are you looking for? A treatise on Hamming graphs? Are you looking for literature? Or are you just looking for the name? The name is “Hamming graph”, you mentioned it. Commented Jun 27, 2013 at 23:00

Do you have all $k^n$ strings of length $n$ using your $k$ symbol alphabet or a selection such as all consecutive 30 letter strings found in the DNA of some individual. The former is a Hamming graph but the latter is "subgraph of a Hamming graph" and I'm not sure how easy it is to say if a given graph can be realized in this way. Although there are restrictions.

Define a "line" to be any maximal clque (set of adjacent points) then 2 points are on at most one line. Then lines have size $k$ or less. Planes are less clear to me.

As commented elsewhere, quasi-Hamming is defined to have the additional condition that distances are the same as in a full Hamming graph so if you have AAAAA and AAABC then you must have one or both of AAABA and AAAAC. There can be triangles and (AAA,BAA,BAX,BCX,BCY,ACY,ACA) would make a cord free $7$-gon. However there can not be a cord free $5$-gon.

• Oh, of course, I did not notice that he might mean that. Commented Jun 28, 2013 at 0:23
• That's correct Aaron this is DNA/RNA strings and I do not have the full set of k^n strings only a subset that are present for a given individual. Commented Jun 28, 2013 at 1:49

These graphs are called Hamming graphs. They are a special cartesian product of graphs, namely the Hamming graph $H(n,d)$ where $n$ is the length of the strings and $d$ the size of the alphabet is the cartesian product of $n$ copies of a complete graphs (without loops) with $d$ vertices. The vertices of $H(n,d)$ are all words of length $n$ over the given alphabet.

Edit If you have only some set of strings of a given length (I assumed that you mean the set of all strings of a given length) then, of course, it is only an induced subgraph of a Hamming graph, as described by Aaron below. I have looked the definition of “partial Hamming graph” up: It is not the same. A partial Hamming graph is a subgraph of a Hamming graph such that—although some vertices might be missing—the distance (length shortest paths) between two vertices is still the Hamming distance.

• Rereading this, your mention of "partial Hamming graph" being "not the same" is a little ambiguous. Do you mean an induced subgraph of a Hamming graph is not the same as a partial Hamming graph? Commented Jun 28, 2013 at 22:46
• Yes, exactly (and it is also not the same as a Hamming graph: every Hamming graph is a partial Hamming graph and every partial Hamming graph is a subgraph of a Hamming graph, but the reverse directions do not hold). Commented Jun 28, 2013 at 22:49