In mathematics, Johnson graphs are a special class of undirected graphs-element subsets-element set; two vertices are adjacent when the intersection-elements. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson.

Special cases

• are the complete graph .

• is the octahedral graph.

• is the complement of the Petersen graph, hence the line graph of is the line graph of and the complement of the Kneser graph

Graph-theoretic properties

• is isomorphic

• 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.

• -vertex-connected.

• forms the vertex-edge graph of an (n−1)-dimensional polytope, called a hypersimplex.

• Any maximal clique.

• The clique number is given by an expression in terms of its least and greatest eigenvalues

• The clique cover number but is not known in general.

• The chromatic number

• Each Johnson graph is locally grid, meaning that the induced subgraph of the neighbors of any vertex is a rook's graph rook's graph.

Automorphism group

There is a distance-transitive subgroup isomorphic.

Intersection array

is also distance-regular denote its diameter is given by

where:

is shared with three other distance-regular graphs that are not Johnson graphs.

Eigenvalues and eigenvectors

• is given by

  The eigenvectors have an explicit description.

Johnson scheme

is closely related to the Johnson scheme, an association scheme in which each pair of -element sets is associated with a number, half the size of the symmetric difference of the two sets. 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.

The Johnson scheme is also related to another family of distance-transitive graphs, the odd graphs-element set and whose edges correspond to disjoint pairs of subsets.

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.

In general, determining the chromatic number of a Johnson graph is an open problem.

See also

• Grassmann graph

References

External links