Махнев А. А., Падучих Д. В.
Новая оценка для числа вершин реберно регулярных графов

Пусть Γ является связным реберно регулярным графом с параметрами (v, k, λ) и b₁ = k - λ - 1. Доказано, что в случае k ≥ 3b₁- 2 либо для любой вершины u верно неравенство |Γ2(u)|(k -2b₁ + 2) < kb₁ , либо Γ является многоугольником, реберным графом тривалентного графа без треугольников, имеющим диаметр, больший 2, графом икосаэдра, полным многодольным графом K_r×2, 3×3-решеткой, треугольным графом T(m), m ≤ 7, графом Клебша или графом Шлефли.

Makhnev A. A., Paduchikh D. V. 
A new estimate for the vertex number of an edge-regular graph

Given a connected edge-regular graph Γ with parameters (v, k, λ) and b₁ = k - λ - 1, we prove that in the case k ≥ 3b₁- 2 either ||Γ2(u)|(k -2b₁ + 2) < kb₁ for every vertex u or Γ is a polygon, the edge graph of a trivalent graph without triangles that has diameter greater than 2, the icosahedral graph, the complete multipartite graph K_r×2, the 3×3-grid, the triangular graph T(m) with m ≤ 7, the Clebsch graph, or the Schlafli graph.

Полный текст статьи / Full texts:

• PDF file (270 KB)
• PostScript file (975 KB)