Читать онлайн «Новая оценка для числа вершин реберно регулярных графов»

Сибирский математический журнал Июль—август, 2007. Том 48, № 4 УДК 519. 14 НОВАЯ ОЦЕНКА ДЛЯ ЧИСЛА ВЕРШИН РЕБЕРНО РЕГУЛЯРНЫХ ГРАФОВ А. А. Махнев, Д. В. Падучих Аннотация: Пусть  является связным реберно регулярным графом с парамет- рами (v, k, λ) и b1 = k − λ − 1. Доказано, что в случае k ≥ 3b1 − 2 либо для любой вершины u верно неравенство |2 (u)|(k − 2b1 + 2) < kb1 , либо  являет- ся многоугольником, реберным графом тривалентного графа без треугольников, имеющим диаметр, больший 2, графом икосаэдра, полным многодольным графом Kr×2 , 3 × 3-решеткой, треугольным графом T (m), m ≤ 7, графом Клебша или графом Шлефли. Ключевые слова: реберно регулярный граф, характеризация по параметрам. Введение Мы рассматриваем неориентированные графы без петель и кратных ребер. Если a, b — вершины графа  , то через d(a, b) обозначается расстояние между a и b, а через i (a) — подграф графа  , индуцированный множеством вершин, которые находятся в  на расстоянии i от вершины a. Подграф 1 (a) называ- ется окрестностью вершины a и обозначается через [a]. Через a⊥ обозначается подграф, являющийся шаром радиуса 1 с центром a. Граф  называется регулярным графом степени k, если [a] содержит k вер- шин для любой вершины a из  . Граф  называется реберно регулярным графом с параметрами (v, k, λ), если  содержит v вершин, является регулярным сте- пени k и каждое ребро  лежит в λ треугольниках. Граф  называется вполне регулярным графом с параметрами (v, k, λ, μ), если  реберно регулярен и под- граф [a] ∩ [b] содержит μ вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Число вершин в [a] ∩ [b] обозначим через λ(a, b) (через μ(a, b)), если d(a, b) = 1 (если d(a, b) = 2), а соот- ветствующий подграф назовем (μ-) λ-подграфом. Пусть  — реберно регулярный граф с параметрами (v, k, λ) и b1 = k −λ−1. Пара вершин u, w называется (почти) хорошей, если d(u, w) = 2 и μ(u, w) равно k − 2b1 + 1 (равно k − 2b1 + 2). Тройка вершин (u; w, z) называется (почти) хорошей, если w, z ∈ 2 (u) и μ(u, w) + μ(u, z) не больше 2k − 4b1 + 3 (равно 2k − 4b1 + 4). Через Km1 ,... ,mn обозначим полный n-дольный граф с долями порядков m1 , . . . , mn . Если m1 = · · · = mn = m, то соответствующий граф обознача- ется через Kn×m . Граф K1,3 называется 3-лапой. Треугольным графом T (m) называется граф с множеством неупорядоченных пар из X в качестве вершин, |X| = m и пары {a, b}, {c, d} смежны тогда и только тогда, когда они имеют Работа выполнена при финансовой поддержке Российского фонда фундаментальных ис- следований (код проекта 05–01–00046) и РФФИ-ГФЕН Китая (код проекта 05–01–39000).  c 2007 Махнев А. А. , Падучих Д. В. 818 А. А. Махнев, Д. В. Падучих общий элемент. Граф на множестве вершин X × Y называется m × n-решеткой, если |X| = m, |Y | = n и вершины (x1 , y1 ), (x2 , y2 ) смежны тогда и только то- гда, когда x1 = x2 или y1 = y2 .