Top Qs
Timeline
Chat
Perspective
Johnson graph
Class of undirected graphs defined from systems of sets From Wikipedia, the free encyclopedia
Remove ads
In mathematics, Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph are the -element subsets of an -element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains -elements.[1] Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson.
Remove ads
Special cases
- Both and are the complete graph Kn.
- is the octahedral graph.[2]
- is the complement of the Petersen graph,[1] hence the line graph of K5. More generally, for all , the Johnson graph is the line graph of Kn and the complement of the Kneser graph
Remove ads
Graph-theoretic properties
- is isomorphic to
- For all , any pair of vertices at distance share elements in common.
- is Hamilton-connected, meaning that every pair of vertices forms the endpoints of a Hamiltonian path in the graph. In particular this means that it has a Hamiltonian cycle.[3]
- It is also known that the Johnson graph is -vertex-connected.[4]
- forms the graph of vertices and edges of an (n − 1)-dimensional polytope, called a hypersimplex.[5]
- Any maximal clique is either of the form for a -element subset and , or of the form for a -element set for , or of the form in the edge case .[6]
- The clique number of is given by an expression in terms of its least and greatest eigenvalues: , or, by the above explicit description of maximal cliques,
- The chromatic number of is at most [7]
- Each Johnson graph is locally grid, meaning that the induced subgraph of the neighbors of any vertex is a rook's graph. More precisely, in the Johnson graph , each neighborhood is a rook's graph.[8]
Remove ads
Automorphism group
There is a distance-transitive subgroup of isomorphic to . In fact, , except that when , .[9]
Intersection array
Summarize
Perspective
As a consequence of being distance-transitive, is also distance-regular. Letting denote its diameter, the intersection array of is given by
where:
It turns out that unless is , its intersection array is not shared with any other distinct distance-regular graph; the intersection array of is shared with three other distance-regular graphs that are not Johnson graphs.[1]
Remove ads
Eigenvalues and eigenvectors
- The characteristic polynomial of is given by
- where [9]
- The eigenvectors of have an explicit description.[10]
Remove ads
Johnson scheme
The Johnson graph is closely related to the Johnson scheme, an association scheme in which each pair of k-element sets is associated with a number, half the size of the symmetric difference of the two sets.[11] The Johnson graph has an edge for every pair of sets at distance one in the association scheme, and the distances in the association scheme are exactly the shortest path distances in the Johnson graph.[12]
The Johnson scheme is also related to another family of distance-transitive graphs, the odd graphs, whose vertices are -element subsets of an -element set and whose edges correspond to disjoint pairs of subsets.[11]
Remove ads
Open problems
The vertex-expansion properties of Johnson graphs, as well as the structure of the corresponding extremal sets of vertices of a given size, are not fully understood. However, an asymptotically tight lower bound on expansion of large sets of vertices was recently obtained.[13]
In general, determining the chromatic number of a Johnson graph is an open problem.[14]
See also
References
External links
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads