共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r,n) such that every n-term graphic sequence π = (d1,d2,...,dn) with term sum σ(π) = d1 + d2 + ... + dn ≥ σ(Kr,r,n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. π has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined. 相似文献
3.
We prove the nonexistence of a distance-regular graph with intersection array {74,54,15;1,9,60} and of distance-regular graphs with intersection arrays
{4r3+8r2+6r+1,2r(r+1)(2r+1),2r2+2r+1;1,2r(r+1),(2r+1)(2r2+2r+1)}