# Is this graph well known?

The vertices of G are the k-subsets of some set of size n. Two k-subsets are connected by an edge of G if their symmetric difference is of size 2. The integers n and k are chosen so that the graph is not trivial.

-

## 1 Answer

That's the Johnson graph: http://en.wikipedia.org/wiki/Johnson_graph

-
Thank you for info. Is it known if those graphs are Hamiltonian? –  w g Apr 21 '12 at 8:05
Yes, they are. The key word is combinatorial gray codes, see for example section 4 in www4.ncsu.edu/~savage/AVAILABLE_FOR_MAILING/survey.ps –  Thomas Kalinowski Apr 21 '12 at 10:22