TOPICS
Search

Bipartite Kneser Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Given two positive integers n and k, the bipartite Kneser graph H(n,k) is the graph whose two bipartite sets of vertices represent the k-subsets and (n-k)-subsets of {1,...,n} and where two vertices are connected if and only if 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).

By definition, H(n,k) is isomorphic to H(n,n-k).

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 showed that H(k,n) is Hamiltonian for n<=27.

H(n,1) is isomorphic to the n-crown graph, H(2k,k) is isomorphic to the order (2k; k)-ladder rung graph, 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_2 square K_n^_
H(2k-1,k-1)bipartite double graph of the odd graph O(k)
H(2k,k)(2n; n)-ladder rung graph
H(2k+1,k)middle layer graph

It has long been conjectured that H(n,k) is Hamiltonian for n>2k, and this was verified by Shields and Savage for n<=27.

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

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

Subject classifications