Let $\Gamma=(X, R)$ denote a finite undirected graph without loops or multiple edges, with vertex set $X$ and edge set $R$. Assume that $\Gamma$ is a connected regular graph. For vertices $u$ and $v$ in $X$, let $\partial_\Gamma(u, v)$ denote the distance between $u$ and $v$. The maximum value of the distance function in $\Gamma$ is called the diameter of $\Gamma$, denoted by $d(\Gamma)$. For all $u\in X$ and for all integers $i$ ($0\leq i\leq d$), set

$ \Gamma_i(u):=\{v\mid v\in X, \partial_\Gamma(u, v)=i\}, \;\Gamma_1(u):=\Gamma(u), $

$\Gamma$ is said to be distance-regular whenever for all integers $h, i, j$ ($0\leq h, i, j\leq d(\Gamma)$) and for all $u, v\in X$ with $\partial_\Gamma(u, v)=h$, the number

$ p^h_{ij}:=|\Gamma_i(u)\cap\Gamma_j(v)| $

(1.1)

is independent of $u, v$. The constants $p^h_{ij}$ are known as the intersection numbers of $\Gamma$. For convenience, set

$ c_i:=p^i_{i-1, 1}\; (1\leq i\leq d(\Gamma)), a_i:=p^i_{i1}\;(0\leq i\leq d(\Gamma)), \\ b_i:=p^i_{i+1, 1}\;(0\leq i\leq d(\Gamma)-1), k_i:=p^0_{ii}\;(0\leq i\leq d(\Gamma)), $

and put $c_0:=0, b_d:=0, k:=k_1.$ Note that $c_1=1, a_0=0, $ and

$ {k_j} = \sum\limits_{i = 0}^{d\left( \Gamma \right)} {p_{ij}^h} = \sum\limits_{i = 0}^{d\left( \Gamma \right)} {p_{ij}^h} ,|X| = 1 + {k_1} + \cdots + {k_d}_{\left( \Gamma \right)} $

(1.2)

The reader is referred to [1-3] for general theory of distance-regular graphs.

The complement $\bar{G}$ of a graph $G$ has the same vertex set as $G$, where vertices $x$ and $y$ are adjacent in $\bar{G}$ if and only if they are not adjacent in $G$.

A simple graph $G$ is called generalized strongly regular with parameters $(v, \lambda, a, b, c)$ if it consists of $v$ vertices such that for any $x, y\in G$,

$ |G(x)\cap G(y)|=\left\{ \begin{array}{ll} \lambda & \hbox{if $x=y$, } \\ a \;\hbox{or}\;b& \hbox{if $x, y$ are adjacent, }\\ c & \hbox{otherwise.} \end{array} \right. $

where $a, b$ are integers such that $b\leq a$. In particular, if $a=b$, then $G$ is called strongly regular with parameters $(v, k, a, c)$. Clearly, strongly regular graphs are generalized strongly regular graphs.

Let $\Gamma=(X, R)$ be the distance-regular graph and $\bar{\Gamma}$ be the complement of $\Gamma$. In this paper, we obtain the following result.

Theorem 1.1  Let $\Gamma=(X, R)$ be the distance-regular graph with diameter $d(\Gamma)\geq2$ and intersection numbers

$ p^h_{j\, t}\;(0\leq h, j, t\leq d(\Gamma)) $

Then the following hold.

(ⅰ)If $d(\Gamma)\geq3$, then $\bar{\Gamma}$ is a generalized strongly regular graph with parameters

$ (|X|, |X|-k-1, |X|-2k+c_2-2, |X|-2k-2, |X|-2k+a_1), $

where $k, c_2$ and $a_1$ are parameters of $\Gamma$.

(ⅱ)If $d(\Gamma)=2$, then $\bar{\Gamma}$ is a strongly regular graph with parameters

$ (|X|, |X|-k-1, |X|-2k+c_2-2, |X|-2k+a_1). $

Moreover, $\bar{\Gamma}$ is connected if and only if $|X|-2k+a_1>0.$

Proof  For any $x, y\in X$ with $\partial_\Gamma(x, y)=l$, where $1\leq l\leq d(\Gamma)$. By (1.1) and (1.2), the number of vertices $z\in X$ satisfying both $\partial_{\bar{\Gamma}}(x, z)=1$ and $\partial_{\bar{\Gamma}}(y, z)=1$ is

$ \sum\limits_{2\leq j\leq d(\Gamma)}\sum\limits_{2\leq t\leq d(\Gamma)}p^l_{j\, t} \quad=\quad\sum\limits_ {2\leq j\leq d(\Gamma)}(k_j-p^l_{j\, 1}-p^l_{j\, 0})\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad=\quad\sum\limits_{2\leq j\leq d(\Gamma)} k_j- \sum\limits_{2\leq j\leq d(\Gamma)} p^l_{j\, 1}-\sum\limits_{2\leq j\leq d(\Gamma)} p^l_{j\, 0}\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad=\quad(|X|-k-1)-(k-p^l_{1\, 1}-p^l_{0\, 1})-(1 -p^l_{1\, 0}-p^l_{0\, 0})\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad=\quad|X|-2k+p^l_{1\, 1}+2p^l_{0\, 1}-2\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad=\quad\left\{ \begin{array}{ll} |X|-2k+a_1, & \hbox{if}\;l=1, \\ |X|-2k+p^l_{1\, 1}-2, &\hbox{if}\;l\not=1. \end{array} \right. $

(ⅰ) Suppose that $x$ and $y$ are two distinct vertices of $\bar{\Gamma}$. If $\partial_{\bar{\Gamma}}(x, y)=1$, then there exists some $l\in\{2, \ldots, d(\Gamma)\}$ such that $\partial_\Gamma(x, y)=l$, which implies that the number of vertices $z\in X$ satisfying both $\partial_{\bar{\Gamma}}(x, z)=1$ and $\partial_{\bar{\Gamma}}(y, z)=1$ is

$ |X|-2k+c_2-2 $

or

$ |X|-2k-2, $

according to $l=2$ or $l\not=2$, respectively. If $\partial_{\bar{\Gamma}}(x, y)\not=1$, then $\partial_\Gamma(x, y)=1$, which implies that the number of vertices $z\in X$ satisfying both $\partial_{\bar{\Gamma}}(x, z)=1$ and $\partial_{\bar{\Gamma}}(y, z)=1$ is $|X|-2k+a_1$. Therefore, the desired result follows.

(ⅱ) Similar to the proof of (i), we have $\bar{\Gamma}$ is a strongly regular graph with parameters

$ (|X|, |X|-k-1, |X|-2k+c_2-2, |X|-2k+a_1). $

Suppose that $\bar{\Gamma}$ is not connected and let $Z$ be a component of $\bar{\Gamma}$. Then a vertex in $Z$ has no common neighbours with a vertex not in $Z$, and so

$ |X|-2k+a_1=0. $

If $|X|-2k+a_1=0$, then any two neighbours of a vertex $x\in\bar{\Gamma}$ must be adjacent, and so the component containing $x$ must be a complete graph, and hence $\bar{\Gamma}$ is a disjoint union of complete graphs.

Let $\mathbb{F}_q$ be a finite field with $q$ elements, where $q$ is a prime power. Let $\mathbb{F}_q^{n}$ be the $n$-dimensional vector space over the finite field $\mathbb{F}_q$. Let $1\leq m\leq n-1$. The Grassmann graph $\Gamma(m, q, n)$ is the graph the vertices of which are the $m$-dimensional subspaces of $\mathbb{F}_q^{n}$, where two vertices are adjacent if and only if they meet in a subspace of dimension $m-1$. It can shown (see[2,Theorem 9.3.3]) that $\Gamma(m, q, n)$ is a distance-regular graph of diameter $\min\{m, n-m\}$.

Example 2.1  For $2\leq m\leq n-2$, let $\bar{\Gamma}(m, q, n)$ be the complement of $\Gamma(m, q, n)$ and

$ \beta=\left[n\atop m\right]_q, \;\alpha= 2q\left[n-m\atop 1\right]_q\left[m\atop 1\right]_q, \;\gamma=\frac{q^m+q^{n-m}-2q}{q-1}. $

Then the following hold.

(ⅰ) If $\min\{m, n-m\}>2$, then $\bar{\Gamma}(m, q, n)$ is a generalized strongly regular graph with parameters

$ (\beta, \beta-\alpha-1, \beta-2\alpha+(q+1)^2-2, \beta-2\alpha-2, \beta-2\alpha+\gamma). $

(ⅱ) If $\min\{m, n-m\}=2$, then $\bar{\Gamma}(m, q, n)$ is a strongly regular graph with parameters

$ (\beta, \beta-\alpha-1, \beta-2\alpha+(q+1)^2-2, \beta-2\alpha+\gamma). $

Let $q, r$ are prime powers. Let $V$ be one of the following spaces equipped with a specified form:

$\bullet$ $[C_d(q)]=\mathbb{F}_q^{2d}$ with a nondegenerate symplectic form;

$\bullet$ $[B_d(q)]=\mathbb{F}_q^{2d+1}$ with a nondegenerate quadratic form;

$\bullet$ $[D_d(q)]=\mathbb{F}_q^{2d}$ with a nondegenerate quadratic form of Witt index $d$;

$\bullet$ $[{}^2D_{d+1}(q)]=\mathbb{F}_q^{2d+2}$ with a nondegenerate quadratic form of Witt index $d$;

$\bullet$ $[{}^2A_{2d}(r)]=\mathbb{F}_q^{2d+1}$ with a nondegenerate Hermitean form $q=r^2$;

$\bullet$ $[{}^2A_{2d-1}(r)]=\mathbb{F}_q^{2d}$ with a nondegenerate Hermitean form $q=r^2$.

A subspace of $V$ is called isotropic whenever the form vanishes completely on this subspace. Maximal isotropic subspaces have dimension $d$. The dual polar graph $\Gamma$ (on $V$) has as vertices the maximal isotropic subspaces; two points $P, Q$ are adjacent if and only if $\dim(P\cap Q)=d-1$. It can shown (see[2,Theorem 9.4.3]) that $\Gamma$ is a distance-regular graph of diameter $d$.

Example 2.2  Let $2\leq d$, and let $e$ be $1, 1, 0, 2, 3/2, 1/2$ in the respective cases

$ [C_d(q)], $[B_d(q)], [D_d(q)], [{}^2D_{d+1}(q)], [{}^2A_{2d}(r)], [{}^2A_{2d-1}(r)] $

Let $\bar{\Gamma}$ be the complement of $\Gamma$ and

$ \beta=\prod\limits_{i=0}^{d-1}(q^{d+e-i-1}+1), \; \alpha= q^e\frac{q^d-1}{q-1}, \; \gamma=q^e-1. $

Then the following hold.

(ⅰ) If $d>2$, then $\bar{\Gamma}$ is a generalized strongly regular graph with parameters

$ (\beta, \beta-\alpha-1, \beta-2\alpha+q-1, \beta-2\alpha-2, \beta-2\alpha+\gamma). $

(ⅱ) If $d=2$, then $\bar{\Gamma}$ is a strongly regular graph with parameters

$ (\beta, \beta-\alpha-1, \beta-2\alpha+q-1, \beta-2\alpha+\gamma). $

Let $Y$ be a finite set of cardinality $q\geq2$. The Hamming graph $H(d, q)$ with diameter $d$ has vertex set $Y^d=\bigotimes\limits_{i=1}^dY$, the cartesian product of $d$ copies of $Y$; two points of $H(d, q)$ are adjacent whenever they differ in precisely one coordinate. It can show (see [2,Theorem 9.2.1]) that $H(d, q)$ is a distance-regular graph of diameter $d$.

Example 2.3  Let $2\leq d$ and $\bar{H}(d, q)$ be the complement of $H(d, q)$. Then the following hold.

(ⅰ) If $d>2$, then $\bar{H}(d, q)$ is a generalized strongly regular graph with parameters

$ (q^d, q^d-d(q-1)-1, q^d-2d(q-1), q^d-2d(q-1)-2, q^d-2d(q-1)+q-2). $

(ⅱ) If $d=2$, then $\bar{H}(d, q)$ is a strongly regular graph with parameters

$ (q^d, q^d-d(q-1)-1, q^d-2d(q-1)-2, q^d-2d(q-1)+q-2). $