О почти хороших парах вершин в реберно регулярных графах

Abstract

Неориентированный v-вершинный граф, в котором степени всех вершин равны к, а каждое ребро принадлежит точно Л треугольникам, называется реберно регулярным с параметрами (ν, κ, λ). Пусть b1 = κ - λ - 1. Пара вершин называется почти хорошей, если эти вершины имеют точно κ - 2b1 + 2 общих соседей. Доказано, что если κ ≥ 3b1 - 3 и для вершины и несмежные вершины ω, z, находящиеся на расстоянии 2 от u, образуют почти хорошие пары с u, то |[u] ∩ [ω] ∩ [z]| > 2. Классифицированы вполне регулярные графы с параметрами (ν, κ, λ, μ) и μ = k - 2b1 + 2.

An edge-regular graph with parameters (ν, κ, λ) is an undirected graph with v vertices in which each vertex has degree κ and every edge belongs to precisely λ triangles. Let b1 = κ - λ - 1. A pair of vertices is said to be almost good if the vertices have exactly κ - 2b1 + 2 common neighbors. We have proved that if κ ≥ 3b1 - 3 and, for a vertex v, two non-adjacent vertices ω, z whose distance from u is 2 form almost good pairs with u, then |[u] ∩ [ω] ∩ [z]| > 2. We have also classified completely regular graphs with parameters (ν, κ, λ, μ) and μ = k - 2b1 + 2.