Том 2, номер 4, 1995 г., Стр. 42-53

УДК 519.14
А. А. Махнёв
О регулярных графах, в которых каждое ребро лежит в большом числе треугольников

Аннотация:
Неориентированный $\upsilon$-вершинный граф, в котором степени всех вершин равны $k$, а каждое ребро лежит точно в $\lambda$ треугольниках, называется реберно регулярным графом с параметрами $(\upsilon,k,\lambda)$. Доказано, что если $3\lambda\ge 2k-5$, то любой реберно регулярный граф с параметрами $\upsilon,k,\lambda$ либо является многоугольником или графом икосаэдра, либо имеет $k=4,\lambda=1$, либо имеет диаметр 2 и содержит не более $2k+4$ вершин.
Библиогр. 2.

Махнёв А. А. ¹
1. Институт математики и механики УрО РАН,
ул. Ковалевской, 16, 620219 Екатеринбург, Россия

Статья поступила 6 апреля 1995 г.