Grassmann graph

In graph theory, 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

is isomorphic to .
For all , the intersection of any pair of vertices at distance is -dimensional.
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.

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

: .

References