Kneser graph | ||||
Vertices: | \binom{n}{k} | |||
Edges: |
\binom{n}{k}\binom{n-k}{k} | |||
Chromatic Number: | \begin{cases}n-2k+2&n\ge2k\ 1&n<2k\end{cases} | |||
Notation: | . |
In graph theory, the Kneser graph (alternatively) is the graph whose vertices correspond to the -element subsets of a set of 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 1956.
The Kneser graph is the complete graph on vertices.
The Kneser graph is the complement of the line graph of the complete graph on vertices.
The Kneser graph is the odd graph ; in particular is the Petersen graph (see top right figure).
The Kneser graph, visualized on the right.
The Kneser graph
K(n,k)
\tbinom{n}{k}
\tbinom{n-k}{k}
The Kneser graph is vertex transitive and arc transitive. When
k=2
(\tbinom{n}{2},\tbinom{n-2}{2},\tbinom{n-4}{2},\tbinom{n-3}{2})
k>2
Because Kneser graphs are regular and edge-transitive, their vertex connectivity equals their degree, except for
K(2k,k)
K(n,k)
\tbinom{n-k}{k},
As conjectured, the chromatic number of the Kneser graph
K(n,k)
n\geq2k
In contrast, the fractional chromatic number of these graphs is
n/k
n<2k
K(n,k)
It is well-known that the Petersen graph is not Hamiltonian, but it was long conjectured that this was the sole exception and that every other connected Kneser graph is Hamiltonian.
In 2003, Chen showed that the Kneser graph contains a Hamiltonian cycle if
n\geq
1 | |
2 |
\left(3k+1+\sqrt{5k2-2k+1}\right).
1 | |
2 |
\left(3k+1+\sqrt{5k2-2k+1}\right)<\left(
3+\sqrt{5 | |
k
n\geq\left(
3+\sqrt{5 | |
a
n=2k+2a
When, the Kneser graph contains no triangles. More generally, when it does not contain cliques of size, whereas it does contain such cliques when . Moreover, although the Kneser graph always contains cycles of length four whenever, for values of close to the shortest odd cycle may have variable length.
The diameter of a connected Kneser graph is
The spectrum of the Kneser graph consists of k + 1 distinct eigenvalues: Moreover
λj
\tbinom{n}{j}-\tbinom{n}{j-1}
j>0
λ0
The Erdős–Ko–Rado theorem states that the independence number of the Kneser graph for
n\geq2k
The Johnson graph is the graph whose vertices are the -element subsets of an -element set, two vertices being adjacent when they meet in a -element set. The Johnson graph is the complement of the Kneser graph . Johnson graphs are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson.
The generalized Kneser graph has the same vertex set as the Kneser graph, but connects two vertices whenever they correspond to sets that intersect in or fewer items. Thus .
The bipartite Kneser graph has as vertices the sets of and items drawn from a collection of 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
\tbinom{n-k}{k}.