Up

Affine polar graphs

Consider a vector space V of dimension d over the finite field with q elements provided with a nondegenerate quadratic form Q. Take the vectors in V as vertices of a graph, and join the vectors u and v when Q(v − u) = 0. The resulting graph is denoted by VO+(d,q) or VO−(d,q), or VO(d,q), when the form Q is hyperbolic, elliptic or parabolic, respectively. (In the first two cases d will be even, in the third case d will be odd.)

The graphs VO+(2e,q) are strongly regular, with parameters v = q2e, k = (qe−1 + 1)(qe − 1), λ = q(qe−2 + 1)(qe−1 − 1) + q − 2, μ = qe−1(qe−1 + 1), r = qe − qe−1 − 1, s = − qe−1 − 1.

The graphs VO−(2e,q) are strongly regular, with parameters v = q2e, k = (qe−1 − 1)(qe + 1), λ = q(qe−2 − 1)(qe−1 + 1) + q − 2, μ = qe−1(qe−1 − 1), r = qe−1 − 1, s = − qe + qe−1 − 1.

The graphs VO(2e+1,q) are not strongly regular.

For details about the local structure of these graphs, see
A.E. Brouwer & E.E. Shult, Graphs with odd cocliques, Eur. J. Combin. 11 (1990) 99-104.

For d = 2 we find that VO−(2,q) is a coclique, and that VO+(2,q) is a q×q grid graph (that is, H(2,q)).

Note that the graphs VO+(2e,2) and VO−(2e,2) have λ = μ − 2 and hence give rise to SBIBDs with parameters 2-(22e, 22e−1 + 2e−1−1, 22e−2+ 2e−1) and 2-(22e, 22e−1 − 2e−1−1, 22e−2 − 2e−1), respectively.

If we take the Hamming scheme H(n,4) and call two vertices adjacent if their distance is even we obtain a strongly regular graph (as was observed in S. Kageyama, G.M. Saha & A.D. Das, Reduction of the number of association classes of hypercubic association schemes, Ann. Inst. Stat. Math. 30 (1978) 115-123). But this is just VO+(2n,2) or VO−(2n,2) (where the sign is (−1)n). Indeed, the weight of a quaternary digit is given by the (elliptic) binary quadratic form x12 + x1x2 + x22.