Kneser Graph - Related Graphs

Related Graphs

The Johnson graph J_n,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 KG_n,2. Johnson graphs are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson.

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 . The bipartite Kneser graph can be formed as a bipartite double 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 and the bipartite Kneser graph H_n,1 is a crown graph.