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
$\begingroup$
$\endgroup$
2
That's the Johnson graph: http://en.wikipedia.org/wiki/Johnson_graph
answered Apr 21, 2012 at 7:52
-
$\begingroup$ Thank you for info. Is it known if those graphs are Hamiltonian? $\endgroup$– w gApr 21, 2012 at 8:05
-
$\begingroup$ 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 $\endgroup$ Apr 21, 2012 at 10:22