Bipartite Kneser Graph

Given two positive integers and , the bipartite Kneser graph is the graph whose two bipartite sets of vertices represent the -subsets and -subsets of and where two vertices are connected if and only if they are in different sets and one is a subset of the other. therefore has vertices and is regular of degree .

By definition, is isomorphic to .

is the bipartite double graph of the Kneser graph .

is connected for . Simpson (1991) showed that the bipartite Kneser graphs are symmetric. Shields and Savage showed that is Hamiltonian for .

is isomorphic to the -crown graph, is isomorphic to the order -ladder rung graph, and is isomorphic to the bipartite double graph of the odd graph . Graphs of the latter class are distance-transitive, and therefore also distance-regular (Brouwer et al. 1989, p. 222).

Special cases are summarized in the following table.

	graph
	6-cycle graph
	cubical graph
	Desargues graph
	-crown graph
	bipartite double graph of the odd graph
	-ladder rung graph
	middle two levels problem

It has long been conjectured that is Hamiltonian for , and this was verified by Shields and Savage for .

Wolfram Web Resources