Grassmann graph | |
---|---|
Named after | Hermann Grassmann |
Vertices | |
Edges | |
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.
There is a distance-transitive subgroup of isomorphic to the projective linear group .
In fact, unless or , ≅ ; otherwise ≅ or ≅ respectively. [1]
As a consequence of being distance-transitive, is also distance-regular. Letting denote its diameter, the intersection array of is given by where:
Grassmann graph | |
---|---|
Named after | Hermann Grassmann |
Vertices | |
Edges | |
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.
There is a distance-transitive subgroup of isomorphic to the projective linear group .
In fact, unless or , ≅ ; otherwise ≅ or ≅ respectively. [1]
As a consequence of being distance-transitive, is also distance-regular. Letting denote its diameter, the intersection array of is given by where: