Гаврилюк А. Л., Махнев А. А.
Вполне регулярные графы и блок-схемы

Исследуются вполне регулярные графы Γ диаметра d, в которых для некоторой вершины a множество вершин, находящихся на расстоянии d от a, является множеством точек 2-схемы, множество блоков которой состоит из пересечений окрестностей точек с множеством вершин, находящихся на расстоянии d-1 от a. Доказано, что подграф, индуцированный множеством точек, является кликой, кокликой или сильно регулярным графом диаметра 2. Для графа диаметра 3 установлено, что указанная конструкция является 2-схемой для любой вершины a тогда и только тогда, когда граф дистанционно регулярен и для любой вершины a подграф Γ₃(a) является кликой, кокликой или сильно регулярным графом. Получен список возможных параметров для схем и графов диаметра 3 при условии, что подграф, индуцированный множеством точек, является графом Зейделя. Показано, что некоторые из найденных параметров не могут отвечать дистанционно регулярным графам.

Gavrilyuk A. L., Makhnev A. A.
Amply regular graphs and block designs

We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ₃(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.

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

• PDF file (465 KB)
• PostScript file (935 KB)