Kneser graph

Kneser graph

infobox graph
name = Kneser graph


image_caption = The Kneser graph "KG"5,2, isomorphic to the Petersen graph
namesake = Martin Kneser
properties = arc-transitive
In graph theory, the Kneser graph KG_{n,k} is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are connected if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1955.

Examples

The complete graph on n vertices is the Kneser graph KG_{n,1}.

The Kneser graph "KG"5,2 is isomorphic to the Petersen Graph.

The Kneser graph KG_{2n-1,n-1} is known as the odd graph O_n.

Properties

* The Kneser graph is a vertex-transitive and edge-transitive graph in which each vertex has exactly n-kchoose k neighbors. However the Kneser graph is not, in general, a strongly regular graph, as different pairs of nonadjacent vertices have different numbers of common neighbors depending on the size of the intersection of the corresponding pair of sets.

* As Kneser (1955) conjectured, the chromatic number of the Kneser graph KG_{n,k} is exactly "n"-2"k"+2; for instance, the Petersen graph requires three colors in any proper coloring. Lovász (1978) proved this using topological methods, giving rise to the field of topological combinatorics, and in 2002 Joshua Greene won the Frank and Brennie Morgan Prize for Outstanding Research in Mathematics by an Undergraduate Student for a simplified but still topological proof. Matoušek (2004) found a purely combinatorial proof.

* When "n" ≥ 3"k", the Kneser graph KG_{n,k} always contains a Hamiltonian cycle (Chen 2000). Computational searches have found that all connected Kneser graphs for "n" ≤ 27, except for the Petersen graph, are Hamiltonian (Shields 2004).

* When "n" < 3"k", the Kneser graph contains no triangles. More generally, although the Kneser graph always contains cycles of length four whenever "n" ≥ 2"k"+2, for values of "n" close to 2"k" the shortest odd cycle may have nonconstant length (Denley 1997).

* The diameter of a connected Kneser graph KG_{n,k} is::leftlceil frac{k-1}{n-2k} ight ceil + 1:(Valencia-Pabon and Vera 2005).

Related graphs

The complement of a Kneser graph is sometimes known as a Johnson graph.

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

The bipartite Kneser graph H_{n,k} has as vertices the sets of "k" and "n"-"k" 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 n-kchoose k. The bipartite Kneser graph can be formed as a bipartite cover of KG_{n,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 "H"5,2 is the Desargues graph.

References

* cite journal
author = Chen, Ya-Chen
journal = Journal of Combinatorial Theory, Series B
title = Kneser graphs are Hamiltonian for "n" ≥ 3"k"
volume = 80
year = 2000
pages = 69–79
url = http://math.la.asu.edu/~cchen/kneser.ps
doi = 10.1006/jctb.2000.1969

* cite journal
title = The odd girth of the generalised Kneser graph
author = Denley, Tristan
journal = European Journal of Combinatorics
volume = 18
issue = 6
year = 1997
pages = 607–611
doi = 10.1006/eujc.1996.0122

* cite journal
author = Greene, Joshua E.
title = A new short proof of Kneser's conjecture
journal = American Mathematical Monthly
year = 2002
volume = 109
issue = 10
pages = 918–920
doi = 10.2307/3072460

* cite journal
author = Kneser, Martin
title = Aufgabe 360
journal = Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung
volume = 58
year = 1955
pages = 27

* cite journal
author = Lovász, László
authorlink = László Lovász
title = Kneser's conjecture, chromatic number, and homotopy
year = 1978
volume = 25
journal = Journal of Combinatorial Theory, Series A
pages = 319–324
doi = 10.1016/0097-3165(78)90022-5

* cite journal
author = Matoušek, Jiří
title = A combinatorial proof of Kneser's conjecture
journal = Combinatorica
volume = 24
issue = 1
year = 2004
pages = 163–170
doi = 10.1007/s00493-004-0011-1

* cite paper
author = Shields, Ian Beaumont
title = Hamilton Cycle Heuristics in Hard Graphs
version = Ph.D. thesis
publisher = North Carolina State University
url = http://www.lib.ncsu.edu/theses/available/etd-03142004-013420/
year = 2004

* cite conference
author = Simpson, J. E.
title = Hamiltonian bipartite graphs
booktitle = Proc. 22nd Southeastern Conf. Combinatorics, Graph Theory, and Computing
pages = 97–110
volume = 85
year = 1991

* cite journal
title = On the diameter of Kneser graphs
author = Valencia-Pabon, Mario; Vera, Juan-Carlos
journal = Discrete Mathematics
volume = 305
issue = 1–3
pages = 383–385
year = 2005
doi = 10.1016/j.disc.2005.10.001

External links

*
*


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Graphe de Kneser — Le graphe de Kneser KG5,2, isomorphe au graphe de Petersen Notation KGn,k Nombre de sommets Distribution des degrés …   Wikipédia en Français

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia

  • Odd graph — The Petersen graph as an odd graph O3 Vertices Edges …   Wikipedia

  • Desargues graph — Named after Gérard Desargues Vertices 20 Edges 30 …   Wikipedia

  • Levi graph — infobox graph name = Levi graph image caption = The Pappus graph, a Levi graph with 18 vertices formed from the Pappus configuration. Vertices labeled with single letters correspond to points in the configuration; vertices labeled with three… …   Wikipedia

  • Crown graph — Crown graphs with six, eight, and ten vertices. In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j. The crown… …   Wikipedia

  • Vertex-transitive graph — In mathematics, a vertex transitive graph is a graph G such that, given any two vertices v1 and v2 of G , there is some automorphism : f : V(G) → V(G) such that : f (v1) = v2. In other words, a graph is vertex transitive if its automorphism group …   Wikipedia

  • List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) …   Wikipedia

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Grushko theorem — In the mathematical subject of group theory, the Grushko theorem or the Grushko Neumann theorem is a theorem stating that the rank (that is, the smallest cardinality of a generating set) of a free product of two groups is equal to the sum of the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”