* The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
* Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).


Notice that this graph has $\frac{n!}{(n-k)!}$ vertices. It is an $k(n-k)$-regular graph.


Does the graph have a name?


A closely related graph is the [Hamming graph](http://mathworld.wolfram.com/HammingGraph.html) (denoted by $H(n,k)$), which does *not* exclude the tuples with duplicate components. It has $k^n$ vertices. It is closely related because the graph I am looking for is the induced subgraph of $H(n,k)$ after removing the vertices corresponding to tuples with repeat components.


Another similar graph is the [Johnson graph](http://mathworld.wolfram.com/JohnsonGraph.html), whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.


The [Kneser graph](http://mathworld.wolfram.com/KneserGraph.html) (and [its generalization](http://en.wikipedia.org/wiki/Kneser_graph#Related_graphs)) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.



Is the following graph well known?
They might have a name, I don't know. For the next few lines let us call each a Partial Permutation graph $PP(n,k)$ (assume $k<n$). They may not get as much respect because they are not distance transitive (which the Hamming, Johnson and Knesser Graphs are) or even distance regular (but see below for the special case $k=n$). The Symmetric Group on the underlying set acts on all 4 kinds of graphs and allows one to map any vertex to any other. Consider $n>4$ and $k=2$. In all 4 cases the maximum distance is 2. In $J(n,2)$ any two non-adjacent vertices such as $\lbrace a,b \rbrace$ & $\lbrace c,d \rbrace$ have 4 mutual neighbors. In $H(n,2)$, $[a,b]$ & $[c,d]$ have two mutual neighbors ($[a,d]$ and $[c,b]$) as do $[a,a]$ & $[c,d]$ or $[a,a]$ & $ [c,c]$ and more importantly $[a,b]$ & $[c,a]$ as well as $[a,b]$ & $[b,a]$. I'll leave Knesser graphs for the reader to consider. In $PP(n,2)$ $[a,b]$ & $[c,d]$ still have two mutual neighbors but $[a,b]$ & $[c,a]$ only have one while $[a,b]$ & $[b,a]$ have none. So there are three ways to be at distance $2$. It is a 5-class association scheme of diameter 2 however. For $k=3$ or $k=4$ there begin to be a great number of associate classes. If I calculate correctly, for $n>2k$ $PP(n,k)$ has diameter $k$ but $\binom{k+1}{2}-1$ associate classes (or orbits on pairs of vertices under the action of the automorphism group if you prefer)


In the special case that $k=n$ one would have a graph with $n!$ vertices each of degree $\binom n2$ (one would have to let adjacency be differing in only two positions). Since that is a Cayley graph for $S\_n$, it is distance transitive. In the more restricted case that adjacency is that two permutations differ only by the swap of two **adjacent** positions it is the skeleton of the [permutohedron](http://en.wikipedia.org/wiki/Permutohedron).


**later** I certainly looked at those graphs at some point. At the time I did not realize that they (seem) to always have all eigenvalues integral (based on a criminally small number of test cases). I wonder if there is an easy way to see that happens (if it does..)


**much later** The graph PP(7,3) actually has 10 associate classes. I had fun so here are the details. A disclaimer, I'm sure that group representation methods are much more efficient if one knows how to use them.I found the classes by making the 210 by 210 adjacency matrix then raising it to the 4th power. Of the 44100 entries, 10 distinct values occur and they reveal what the classes are (although once you know it is obvious!). Then the adjacency matrix (or simple combinatorics) reveals the numbers. The relation depends on the number of entries equal in value and in the same place and also the number of entries equal but not in the same place. And then more. Note that with respect to 123, both 214 and 241 have one new symbol, but 123 and 214 are at distance 4 (say 123 124 154 254 214) while 123 143 243 241 is a distance 3 path.


distance 0: 123 (itself)


distance 1: 124


distance 2: 134 145


distance 3: 234 245 456 132


distance 4: 214 231


distance 0: 123 (itself)


distance 1: 124


distance 2: 145 134


distance 3: 132 456 451 432


distance 4: 214 231


Each vertex (such as u=123) is adjacent to 12 other vertices. If v is a vertex in class i with respect to u then row i in this matrix shows in column j how many of the 12 neighbors of u are in class j with respect to v. Then we find that the eigenvalues of this small matrix are [12,8,5,4,3,1,0,-3,-3,-3] The repeated eigenvalue -3 was what made me suspect that there were 8 classes. `


$$ \left[ \begin {array}{cccccccccc} 
0&12&0&0&0&0&0&0&0&0
\\ 1&3&6&2&0&0&0&0&0&0\\ 0&2&4&2&0
&2&2&0&0&0\\ 0&1&3&3&1&0&3&1&0&0
\\ 0&0&0&8&0&0&0&0&4&0\\ 0&0&3&0&0
&3&6&0&0&0\\ 0&0&1&1&0&2&5&2&1&0
\\ 0&0&0&1&0&0&6&3&1&1\\ 0&0&0&0&1
&0&6&2&3&0\\ 0&0&0&0&0&0&0&12&0&0\end {array}\right] $$
Further analysis is possible, such as finding nice eigenvectors and substructures, but I still suspect that someone knows all this.


