Related Graphs
The Johnson graph Jn,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 KGn,2. Johnson graphs are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson.
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 double 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 and the bipartite Kneser graph Hn,1 is a crown graph.
Read more about this topic: Kneser Graph
Famous quotes containing the word related:
“No being exists or can exist which is not related to space in some way. God is everywhere, created minds are somewhere, and body is in the space that it occupies; and whatever is neither everywhere nor anywhere does not exist. And hence it follows that space is an effect arising from the first existence of being, because when any being is postulated, space is postulated.”
—Isaac Newton (1642–1727)