The graph Kre(4) does not exist |
| |
Authors: | Email author" target="_blank">A?A?MakhnevEmail author |
| |
Institution: | 1.Institute of Mathematics and Mechanics, Ural Branch,Russian Academy of Sciences,Yekaterinburg,Russia;2.Ural Federal University,Yekaterinburg,Russia |
| |
Abstract: | Suppose that a strongly regular graph Γ with parameters (v, k, λ, μ) has eigenvalues k, r, and s. If the graphs Γ and \(\bar \Gamma \) are connected, then the following inequalities, known as Krein’s conditions, hold: (i) (r + 1)(k + r + 2rs) ≤ (k + r)(s + 1)2 and (ii) (s + 1)(k + s + 2rs) ≤ (k + s)(r + 1)2. We say that Γ is a Krein graph if one of Krein’s conditions (i) and (ii) is an equality for this graph. A triangle-free Krein graph has parameters ((r 2 + 3r)2, r 3 + 3r 2 + r, 0, r 2 + r). We denote such a graph by Kre(r). It is known that, in the cases r = 1 and r = 2, the graphs Kre(r) exist and are unique; these are the Clebsch and Higman–Sims graphs, respectively. The latter was constructed in 1968 together with the Higman–Sims sporadic simple group. A.L. Gavrilyuk and A.A. Makhnev have proved that the graph Kre(3) does not exist. In this paper, it is proved that the graph Kre(4) (a strongly regular graph with parameters (784, 116, 0, 20)) does not exist either. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|