TOPICS

# 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.

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

The -bipartite Kneser graph is implemented in the Wolfram Language as GraphData["BipartiteKneser", n, k].

Bipartite Double Graph, Bipartite Graph, Crown Graph, Kneser Graph, Middle Layer Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Chen, B. L. and Lih, K.-W. "Hamiltonian Uniform Subset Graphs." J. Combin. Th. Ser. B 42, 257-263, 1987.Dejter, I. J. "Some Hamilton Cycles in Bipartite Reflective Kneser Graphs." Technical Report. Univ. of Puerto Rico.Dejter, I. J.; Cordova, J.; and Quintana, J. A. "Two Hamilton Cycles in Bipartite Reflective Kneser Graphs." In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986). Vol. 72, pp. 63-70, 1988.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." http://www.cybershields.com/publications/kneser3.pdf.Simpson, J. E. "Hamiltonian Bipartite Graphs." In Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991). Vol. 85, pp. 97-110, 1991.

## Referenced on Wolfram|Alpha

Bipartite Kneser Graph

## Cite this as:

Weisstein, Eric W. "Bipartite Kneser Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BipartiteKneserGraph.html