TOPICS
Search

Bipartite Kneser Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The bipartite Kneser graph H(n,k), for integers n>=2k>=2, is the graph whose two disjoint parts of vertices represent the k-subsets and (n-k)-subsets of {1,...,n} and where two vertices are connected iff they are in different sets and one is a subset of the other. H(n,k) therefore has 2(n; k) vertices and is regular of degree (n-k; k).

When n=2k, the two parts are distinct copies of the same collection of subsets.

H(n,k) is the bipartite double graph of the Kneser graph K(n,k).

H(n,k) is connected for n>2k. Simpson (1991) showed that the bipartite Kneser graphs are symmetric. Shields and Savage verified that H(n,k) is Hamiltonian for n>2k with n<=27.

H(n,1) is isomorphic to the n-crown graph, H(2k,k) is isomorphic to the ladder rung graph consisting of (2k; k) disjoint edges, and H(2k-1,k-1) is isomorphic to the bipartite double graph of the odd graph O(k). 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.

H(n,k)graph
H(3,1)cycle graph C_6
H(4,1)cubical graph Q_3
H(5,2)Desargues graph GP(10,3)
H(7,3)Danzer graph
H(n,1)crown graph K_(n,n)-M
H(2k-1,k-1)bipartite double graph of the odd graph O(k)
H(2k,k)(2k; k)-ladder rung graph
H(2k+1,k)middle layer graph

Mütze and Su (2017) proved that H(n,k) is Hamiltonian for every n>2k>=2, settling the earlier conjecture.

For a prime p>3 with p=3 (mod8), Metzger and Ulrigg (2026) proved that the orientable genus of H(p,2) is

gamma(H(p,2))=1-(p(p-1))/2+(p(p-1)(p-2)(p-3))/(16).

They constructed an orientable graph embedding in which every face has four sides.

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

See also

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

Explore with Wolfram|Alpha

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.DistanceRegular.org. "Kneser Graphs." https://www.math.mun.ca/distanceregular/indexes/knesergraphs.html.House of Graphs. Bipartite Kneser Graphs. C_6, The cube Q_3, Desargues Graph (GP(10,3)), and Danzer Graph.Metzger, A. and Ulrigg, A. "The Genus of Bipartite Kneser Graphs." 2 Oct 2026. https://arxiv.org/abs/2610.03159.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Math. Soc. 71, 583-592, 2024.Mütze, T. and Su, P. "Bipartite Kneser Graphs Are Hamiltonian." Combinatorica 37, 1207-1219, 2017. https://doi.org/10.1007/s00493-016-3434-6.Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." https://web.archive.org/web/20040919084100/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 Resource. https://mathworld.wolfram.com/BipartiteKneserGraph.html

Subject classifications