Kneser graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For the Kneser neighborhood graph of unimodular lattices, see Niemeier lattice.
Kneser graph
Kneser graph KG(5,2).svg
The Kneser graph KG5,2,
isomorphic to the Petersen graph
Named after Martin Kneser
Vertices \textstyle\binom{n}{k}
Edges \textstyle\binom{n}{k} \binom{n - k}{k} / 2
Chromatic number \left\{\begin{array}{ll}n - 2 k + 2 & n \ge 2 k\\ 1 & \text{otherwise}\end{array}\right.
Properties \textstyle\binom{n - k}{k}-regular
Notation KGn,k, K(n,k)

In graph theory, the Kneser graph KGn,k is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1955.


The complete graph on n vertices is the Kneser graph KGn,1.

The complement of the line graph of the complete graph on n vertices is the Kneser graph KGn,2.

The Kneser graph KG2n − 1,n − 1 is known as the odd graph On; the odd graph O3 = KG5,2 is isomorphic to the Petersen graph.


For j=0,...,k, the eigenvalue \lambda_j=(-1)^j\binom{n-k-j}{k-j} occurs with multiplicity \binom{n}{j}-\binom{n}{j-1} for  j > 0 and 1 for j = 0 . See this paper for a proof.

Related graphs[edit]

The Johnson graph Jn,k is the graph whose vertices are the k-element subsets of an n-element set, two vertices being adjacent when they meet in a (k − 1)-element set. For k = 2 the Johnson graph is the complement of the Kneser graph KGn,2. Johnson graphs are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson.

The generalized Kneser graph KGn,k,s has the same vertex set as the Kneser graph KGn,k, but connects two vertices whenever they correspond to sets that intersect in s or fewer items (Denley 1997). Thus KGn,k,0 = KGn,k.

The bipartite Kneser graph Hn,k has as vertices the sets of k and nk items drawn from a collection of n elements. Two vertices are connected by an edge whenever one set is a subset of the other. Like the Kneser graph it is vertex transitive with degree \textstyle\binom{n-k}{k}. The bipartite Kneser graph can be formed as a bipartite double cover of KGn,k in which one makes two copies of each vertex and replaces each edge by a pair of edges connecting corresponding pairs of vertices (Simpson 1991). The bipartite Kneser graph H5,2 is the Desargues graph and the bipartite Kneser graph Hn,1 is a crown graph.


External links[edit]