Grassmann graph

Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph are the -dimensional subspaces of an -dimensional vector space over a finite field of order ; two vertices are adjacent when their intersection is -dimensional.

Grassmann Graph
Named afterHermann Grassmann
Vertices
Edges
Diameter
PropertiesDistance-transitive
Connected
Notation
Table of graphs and parameters

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

Graph-theoretic properties

  • is isomorphic to .
  • For all , the intersection of any pair of vertices at distance is -dimensional.
  • which is to say that the clique number of is given by an expression in terms its least and greatest eigenvalues and .

Automorphism group

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

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

Intersection array

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

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

See also

References

  1. Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.