Welcome to MathOverflow

Question

2

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.

flag	asked Apr 21 2012 at 7:47 w g 85●3

Thomas Kalinowski · Accepted Answer · 2012-04-21 07:52:31Z UTC

5

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

answered Apr 21 2012 at 7:52

Thomas Kalinowski
709●4●7

	Thank you for info. Is it known if those graphs are Hamiltonian? – w g Apr 21 2012 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 2012 at 10:22

Is this graph well known?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.