Class of simple graphs defined from vector spaces
Grassmann graph |
---|
Named after | Hermann Grassmann |
---|
Vertices | ![{\displaystyle {\binom {n}{k}}_{q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53eeb3a1e73e0f51fc7f139157df9e3116cb1beb) |
---|
Edges | ![{\displaystyle {\frac {q[k]_{q}[n-k]_{q}}{2}}{\binom {n}{k}}_{q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/453131d1cbc3c106d79353e94ed26db5af93a5ad) |
---|
Diameter | min(k, n – k) |
---|
Properties | Distance-transitive Connected |
---|
Notation | Jq(n,k) |
---|
Table of graphs and parameters |
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.
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
- Jq(n, k) is isomorphic to Jq(n, n – k).
- For all 0 ≤ d ≤ diam(Jq(n,k)), the intersection of any pair of vertices at distance d is (k – d)-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
There is a distance-transitive subgroup of
isomorphic to the projective linear group
.[citation needed]
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
- ^ a b Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.