Grassmann graph

Summary

In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph Jq(n, k) are the k-dimensional subspaces of an n-dimensional vector space over a finite field of order q; two vertices are adjacent when their intersection is (k – 1)-dimensional.

Grassmann graph
Named afterHermann Grassmann
Vertices
Edges
Diametermin(k, nk)
PropertiesDistance-transitive
Connected
NotationJq(n,k)
Table of graphs and parameters

Many of the parameters of Grassmann graphs are q-analogs of the parameters of Johnson graphs, and Grassmann graphs have several of the same graph properties as Johnson graphs.

Graph-theoretic properties edit

  • Jq(n, k) is isomorphic to Jq(n, nk).
  • For all 0 ≤ d ≤ diam(Jq(n,k)), the intersection of any pair of vertices at distance d is (kd)-dimensional.
  • The clique number of Jq(n,k) is given by an expression in terms its least and greatest eigenvalues λ min and λ max:
 [citation needed]

Automorphism group edit

There is a distance-transitive subgroup of   isomorphic to the projective linear group  .

In fact, unless   or  ,    ; otherwise     or     respectively.[1]

Intersection array edit

As a consequence of being distance-transitive,   is also distance-regular. Letting   denote its diameter, the intersection array of   is given by   where:

  •   for all  .
  •   for all  .

Spectrum edit

  • The characteristic polynomial of   is given by
 .[1]

See also edit

References edit

  1. ^ a b Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.