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!



What type of Hamming Graph is this?
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.


