Kneser graphs

Let k,n be positive integers with kn. The Kneser graphMathworldPlanetmath Kn:k has as its vertex set the (nk) k-element subsets of {1,2,,n}. Two vertices are adjacent if and only if they correspond to disjoint subsets.

The graph Kn:1 is the complete graphMathworldPlanetmath on n vertices. Another well-known Kneser graph is K5:2, better known as the Petersen graphMathworldPlanetmath, which is shown in figure 1. The Petersen graph is often a counterexample to graph-theoretical conjectures.

Figure 1: The Petersen graph
Title Kneser graphs
Canonical name KneserGraphs
Date of creation 2013-03-22 14:16:49
Last modified on 2013-03-22 14:16:49
Owner justice (4961)
Last modified by justice (4961)
Numerical id 5
Author justice (4961)
Entry type Definition
Classification msc 05C99
Defines Petersen graph