Kneser graph
From Wikipedia, the free encyclopedia
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 connected if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1955.
Contents |
[edit] Examples
The complete graph on n vertices is the Kneser graph KGn,1.
The graph KG5,2 is the Petersen Graph.
The Kneser graph KG2n − 1,n − 1 is known as the odd graph On.
[edit] Properties
- The Kneser graph is a vertex-transitive and edge-transitive graph in which each vertex has exactly
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 KGn,k is exactly n-2k+2; for instance, the Petersen graph requires three colors in any proper coloring. Lovász (1978) proved this using topological methods, 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 ≥ 3k, the Kneser graph KGn,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 < 3k, the Kneser graph contains no triangles. More generally, although the Kneser graph always contains cycles of length four whenever n ≥ 2k+2, for values of n close to 2k the shortest odd cycle may have nonconstant length (Denley 1997).
- The diameter of a connected Kneser graph KGn,k is
-
- (Valencia-Pabon and Vera 2005).
[edit] Related graphs
The complement of a Kneser graph is sometimes known as a Johnson graph.
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 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 . The bipartite Kneser graph can be formed as a bipartite 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.
[edit] References
- Chen, Ya-Chen (2000). "Kneser graphs are Hamiltonian for n ≥ 3k". Journal of Combinatorial Theory, Series B 80: 69–79.
- Denley, Tristan (1997). "The odd girth of the generalised Kneser graph". European Journal of Combinatorics 18 (6): 607–611. DOI:10.1006/eujc.1996.0122.
- Greene, Joshua E. (2002). "A new short proof of Kneser's conjecture". American Mathematical Monthly 109 (10): 918–920.
- Kneser, Martin (1955). "Aufgabe 360". Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung 58: 27.
- Lovász, László (1978). "Kneser's conjecture, chromatic number, and homotopy". Journal of Combinatorial Theory, Series A 25: 319–324.
- Matoušek, Jiří (2004). "A combinatorial proof of Kneser's conjecture". Combinatorica 24 (1): 163–170. DOI:10.1007/s00493-004-0011-1.
- Shields, Ian Beaumont. "Hamilton Cycle Heuristics in Hard Graphs". Ph.D. thesis. North Carolina State University.
- Simpson, J. E. (1991). "Hamiltonian bipartite graphs". Proc. 22nd Southeastern Conf. Combinatorics, Graph Theory, and Computing 85: 97–110.
- Valencia-Pabon, Mario; Vera, Juan-Carlos (2005). "On the diameter of Kneser graphs". Discrete Mathematics 305 (1–3): 383–385.
[edit] External links
- Eric W. Weisstein, Kneser Graph at MathWorld.
- Eric W. Weisstein, Odd Graph at MathWorld.
