![]() | ||
Vertices ( n k ) {\displaystyle {\binom {n}{k}}} Edges k ( n − k ) 2 ( n k ) {\displaystyle {\frac {k(n-k)}{2}}{\binom {n}{k}}} Diameter min ( k , n − k ) {\displaystyle \min(k,n-k)} Properties ( k ( n − k ) ) {\displaystyle (k(n-k))} -regularVertex-transitiveDistance-transitiveHamilton-connected Notation J ( n , k ) {\displaystyle J(n,k)} |
Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph
Contents
Special cases
Properties
In the Johnson graph, the distance between every two vertices is half of the Hamming distance between the sets corresponding to the vertices. Johnson graphs are distance-transitive graphs: there is a graph automorphism mapping any pair of vertices to any other pair at the same distance.
As a consequence of being distance-transitive, every Johnson graph is also distance-regular. This means that, for every possible distance
Every Johnson graph 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. Every Johnson graph J(n,k) forms the graph of vertices and edges of an (n − 1)-dimensional polytope, called a hypersimplex.
The eigenvectors of Johnson graph have an explicit description.
The vertex-expansion properties of Johnson graph, 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. It is also known that the Johnson graph
Relation to Johnson scheme
The Johnson graph
The Johnson scheme is also related to another family of distance-transitive graphs, the odd graphs, whose vertices are