🌐 US-Proxy
id="topics">
TOPICS
Search

Kneser Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
KneserGraphs

The Kneser graphs are a class of graph introduced by Lovász (1978) to prove Kneser's conjecture. Given two positive integers n and k with 1<=k<=n, the Kneser graph K(n,k), often denoted K_(n:k) (Godsil and Royle 2001; Pirnazar and Ullman 2002; Scheinerman and Ullman 2011, pp. 31-32), is the graph whose vertices represent the k-subsets of {1,...,n}, and where two vertices are connected iff they correspond to disjoint subsets. K(n,k) therefore has (n; k) vertices and is regular of degree (n-k; k).

K(n,k) is connected for n>2k. For n>=2k, the chromatic number is given by n-2k+2, as conjectured by Kneser (1956) and proved by Lovász (1978), Bárány (1978), Greene (2002), and Matoušek (2004).

K(n,k) has clique number

omega(K(n,k))=|_n/k_|.
(1)

A clique corresponds to pairwise disjoint k-subsets, so its size is at most |_n/k_| and this bound is attainable. A generalization of Baranyai's theorem by Brouwer and Schrijver (1979) gives the clique covering number

theta(K(n,k))=[(|K(n,k)|)/(omega(K(n,k)))]
(2)
=[((n; k))/(|_n/k_|)]
(3)

(S. Wagon, pers. comm., Feb. 12, 2013). When k divides n, this reduces to (n-1; k-1). The fractional chromatic number of Kneser graphs K(n,k) with n>=2k is n/k (Scheinerman and Ullman 2011, p. 32).

Similarly, for n>=2k, the independence number is given by

alpha(K(n,k))=(n-1; k-1)
(4)

by the Erdős-Ko-Rado theorem (Aigner and Ziegler 2000, p. 251).

Östergård et al. (2015) give bounds on the domination numbers of Kneser graphs, together with a number of exact values for smaller cases.

The Kneser graph is the generalization of the odd graph, with the odd graph O_n corresponding to K(2n-1,n-1). Special cases are summarized in the table below.

K(n,k)special case
K(5,2)Petersen graph
K(n,1)n-complete graph K_n
K(n,n-1), n>=3n-empty graph K^__n
K(2n,n)ladder rung graph (1/2(2n; n))P_2

For n>=5, the Kneser graph K(n,2) is distance-regular with intersection array {(n-2)(n-3)/2,2n-8;1,(n-3)(n-4)/2}. Its graph complement is the triangular graph T_n.

Chen and Lih (1987) showed that K(n,k) is symmetric. Merino et al. (2023) proved that, for n>2k and k>=1, K(n,k) is Hamiltonian except for the Petersen graph K(5,2). This was previously verified by Shields and Savage (2004) for n<=27.

K(7,2) is one of the three locally Petersen graphs (Hall 1980).

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

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

See also

Bipartite Kneser Graph, Kneser's Conjecture, Locally Petersen Graph, Odd Graph, Petersen Graph, Triangular Graph

Portions of this entry contributed by Margherita Barile

Explore with Wolfram|Alpha

References

Aigner, M. and Ziegler, G. M. "The Chromatic Number of Kneser Graphs." Ch. 38 in Proofs from the Book, 2nd ed. New York: Springer-Verlag, pp. 251-256, 2000.Bárány, I. "A Short Proof of Kneser's Conjecture." J. Combin. Th., Ser. A 25, 325-326, 1978.Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin, Germany: Springer-Verlag, p. 25, 2008.Brouwer, A. E. "Kneser Graphs." https://aeb.win.tue.nl/drg/graphs/Kneser.html.Brouwer, A. E. and Schrijver, A. "Uniform Hypergraphs." In Packing and Covering in Combinatorics. Mathematical Centre Tracts, No. 106, pp. 39-73, 1979.Chen, B. L. and Lih, K.-W. "Hamiltonian Uniform Subset Graphs." J. Combin. Th. Ser. B 42, 257-263, 1987.Chen, Y.-C. "Kneser Graphs Are Hamiltonian for n>=3k." J. Combin. Th. Ser. B 80, 69-79, 2000.DistanceRegular.org. "Kneser Graphs." https://www.math.mun.ca/distanceregular/indexes/knesergraphs.html.Godsil, C. and Royle, G. "Kneser Graphs." Ch. 7 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 135-161, 2001.Greene, J. E. "A New Short Proof of Kneser's Conjecture." Amer. Math. Monthly 109, 918-920, 2002.Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.Heinrich, K. and Wallis, W. D. "Hamiltonian Cycles in Certain Graphs." J. Austral. Math. Soc. Ser. A 2, 89-98, 1978.Kneser, M. "Aufgabe 300." Jahresber. Deutsch. Math.-Verein 58, 1955.Lovász, L. "Kneser's Conjecture, Chromatic Numbers and Homotopy." J. Comb. Th. A 25, 319-324, 1978.Matoušek, J. "A Combinatorial Proof of Kneser's Conjecture." Combinatorica 24, 163-170, 2004.Merino, A.; Mütze, T.; and Namrata. "Kneser Graphs Are Hamiltonian." Extended abstract. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023) (Ed. B. Saha and R. A. Servedio). New York: ACM, pp. 963-970, 2023. https://doi.org/10.1145/3564246.3585137. Full proof: 24 Feb 2025. https://arxiv.org/abs/2212.03918v4.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Math. Soc. 71, 583-592, 2024.Östergård, P. R. J.; Shao, Z.; and Xu, X. "Bounds on the Domination Number of Kneser Graphs." Ars Math. Contemp. 9, 197-205, 2015.Phillips, D. "Kneser Graph Maximal Neighbour Simplexes." http://www.ucalgary.ca/~phillips/users/sali/kneser.html.Pirnazar, A. and Ullman, D. H. "Girth and Fractional Chromatic Number of Planar Graphs." J. Graph Th. 39, 201-217, 2002.Scheinerman, E. R. and Ullman, D. H. Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, 2011.Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." Bull. Inst. Combin. Appl. 40, 13-22, 2004.

Referenced on Wolfram|Alpha

Kneser Graph

Cite this as:

Weisstein, Eric W., with contributions by Margherita Barile. "Kneser Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KneserGraph.html

Subject classifications