Grassmann graph

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Grassmann Graph
Named afterHermann Grassmann
Vertices
Edges
Diameter
PropertiesDistance-transitive
Connected
Notation
Table of graphs and parameters

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.

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[edit]

  • 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[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]

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.