What type of Hamming Graph is this?

Question

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!

Answer 1

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.

Answer 2

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.