×

A quasi-spectral characterization of strongly distance-regular graphs. (English) Zbl 0956.05103

Electron. J. Comb. 7, No. 1, Research paper R51, 9 p. (2000); printed version J. Comb. 7, No. 2 (2000).
A graph \(\Gamma\) with diameter \(d\) is strongly distance-regular if \(\Gamma\) is distance-regular and its distance-\(d\) graph is strongly regular. It has been conjectured that a strongly distance-regular graph is antipodal or has diameter at most three. Let \(\Gamma\) be a graph with spectrum \(\{\lambda_0^{m_0},\dots,\lambda_d^{m_d}\}\), where \(\lambda_0>\cdots >\lambda_d\), and let \(n=|V(\Gamma)|\). Let \(\pi_i=\prod_{j\neq i}|\lambda_i-\lambda_j|\), \(\sigma_e=m_2+m_4+\cdots \), \(\sigma_o=m_1+m_3+\cdots \), \(\Sigma_e=\pi_0/\pi_2+\pi_0/\pi_4+\cdots \), \(\Sigma_o=\pi_0/\pi_1+\pi_0/\pi_3+\cdots \), for \(u\in V\) let \(k_{d-1}(u)= |\Gamma_{d-1}(u)|\) and let \(H={\displaystyle \frac{n}{\sum_{u\in V}1/k_{d-1}(u)}}\). The main result of this paper is the following Theorem 2.2: A regular graph \(\Gamma\) with \(n\) vertices, eigenvalues \(\lambda_0>\cdots >\lambda_d\), and parameters \(\sigma_e\) and \(\Sigma_e\) as above, is strongly distance-regular if and only if \[ H=n-\frac{n\sigma_e \sigma_o}{n\Sigma_e \Sigma_o+(\sigma_e-\Sigma_e) (\sigma_o+\Sigma_o)}. \]

MSC:

05E30 Association schemes, strongly regular graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite
Full Text: EuDML EMIS