25 июля 2020г.
Введение
В данной работе рассматриваются неориентированные графы без петель и кратных ребер. Если 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] содержит μ вершин в случае d(a, b) = 2. Число вершин в [a]∩[b] обозначим через λ(a, b)(через μ(a, b)), если d(a, b) = 1 (если d(a, b) = 2), а соответствующий подграф назовем λ-(μ-)подграфом. Ректаграфом называется вполне регулярный граф с λ = 0, μ = 2. Если Δ – подграф графа Г и a, b Î Δ, то через dΔ(a, b) обозначим расстояние между a и b. Связный граф называется дистанционно регулярным с массивом пересечений {b0, b1,…, bd–1 ; c1, c2,…, cd}, если существуют неотрицательные целые числа bi, ci(i ≥ 0), такие что для любых двух точек x, yÎГ, находящихся на расстоянии i = d(x,y) существует точно ci вершин, смежных с вершиной y в Гi–1(x) и bi вершин, смежных с
вершиной y в Гi–1(x). Блок-схемой с параметрами (v, b, r, k, λ) называют упорядоченную пару (X, ℬ), где X – конечное множество, содержащее v точек. ℬ Í 2X, причём |ℬ| = b: B1, B2, …Bb, таких что, |Bi| = k для любого iÎ{1,…,b} (т.е. каждый блок инцидентен ровно k точкам), каждая точка инцидентна ровно r блокам и любые две точки лежат точно в λ блоках.
В работе [2] доказана следующая теорема.
Теорема 2. Пусть Г является сильно регулярным графом с параметрами (352, 26, 0, 2), G = Aut(Г), g– элемент простого порядка р из G и Δ = Fix(g). Тогда выполняется одно из следующих утверждений:
(1) р = 2 и либо Δ – пустой граф, 14-коклика или связный граф степени 6 на 32 вершинах, либо Δ имеет 4 связные компоненты, являющиеся четырехугольниками;
(2) р = 5 и Δ − двухвершинная клика;
(3) р = 13 и Δ является одновершинным графом.
В этом утверждении строение всех графов очевидно, за исключением связного графа, степени 6 на 32 вершинах. Именно строению этого графа посвящена данная статья.
Строение Г2(a) вполне регулярного графа с параметрами (32, 6, 0, 2)
Теорема 1 Пусть а – некоторая, фиксированная вершина вполне регулярного графа Г с параметрами (32, 6, 0, 2). Тогда ([a], Г2(а)) – блок-схема с параметрами (6, 15, 5, 2, 1).
Доказательство. Пусть a – некоторая вершина графа. Тогда [a] содержит 6 вершин: a1, a2, a3, a4, a5,a6. Т.к. граф регулярный, то каждая вершина из [a] смежна точно с пятью вершинами из Г2(a).
Из прямоугольного соотношения k(k – λ –1) = |Г2(a)|μ, получаем, что |Г2(a)| = 15. Обозначим множество всех вершин Г2(a) = {b1, b2,…, b15}.
Пусть, теперь, вершина a1 смежна с вершинами b1, b2, b3, b4 и b5. из Г2(a). Т.к. вершины a1 и a2 находятся на расстоянии 2 (они обе смежны с вершиной a), то в Г2(a) есть ещё одна вершина, которая смежна с ними обоими. Пусть эта вершина будет b1. Т.к. мы предполагаем, что граф вполне регулярный и μ(a1, a2) = {a, b1}, то других вершин, смежных с вершинами a1 и a2 в Г2(a) не существует. Но, |μ(a1, a3)| = 2. Поэтому в μ(a1, a3) существует ещё одна вершина, смежная с a1 и a3 и это не может быть b1, т.к. в этом случае, μ(a, b1) = {a1, a2, a3}. Не умаляя общности можно считать, что μ(a1, a3) = {a, b2}. Рассуждая аналогично, получим: μ(a1, a2) = {a, b1}, μ(a1, a3) = {a, b2}, μ(a1, a4) = {a, b3}, μ(a1, a5) = {a, b4}, μ(a1, a6) = {a, b5}.
Пусть X1 = {b1, b2, b3, b4, b5}. Это все те вершины из Г2(a), с которыми смежна вершина a1. Обозначим через X2 множество всех вершин из Г2(a), смежных с a2, но не смежных с a1. Т.к. μ(a1, a2) = {a, b1}, то |X2| = 4. Не умаляя общности, можно считать, что X2 = {b6, b7, b8, b9}. Т.к. |μ(a2, a3)| = 2 и a Î μ(a1, a3), то в Г2(a) существует единственная вершина, смежная с a2, и a3. Пусть это будет b6. Тогда можно считать, что μ(a2, a3) = {a, b6}, μ(a2, a4) = {a, b7}, μ(a2, a5) = {a, b8}, μ(a2, a6) = {a, b9}. Обозначим через X3 множество всех вершин из Г2(a), смежных с a3, но не смежных ни с вершиной a2, ни с вершиной a1. Т.к μ(a1, a3) = {a, b2} и μ(a2, a3) = {a, b6}, то |X3| = 3. Не умаляя общности можно считать, что X3 = {b10, b11, b12}. Рассуждая аналогично, можно считать, что μ(a3, a4) = {a, b10}, μ(a3, a5) = {a, b11}, μ(a3, a6) = {a, b12}.
Обозначим через X4 множество всех вершин из Г2(a), смежных с a4, но не смежных ни с вершиной a3, ни с вершиной a2, ни с вершиной a1.
Т.к μ(a1, a4) = {a, b3}, μ(a2, a4) = {a, b7} и μ(a3, a4) = {a, b10}, то |X4| = 2. Не умаляя общности можно считать, что X4 = {b13, b14}. Рассуждая аналогично, можно считать, что μ(a4, a5) = {a, b13}, μ(a4, a6) = {a, b14}. Тогда, в Г2(a) осталась только одна вершина b15, смежная с a5 и a6. X5 = {b15}. Теорема доказана.
Обозначим через αi количество вершин графа Г2(а), смежных с вершиной bi, лежащих в Г3(а). Тогда, поскольку степень графа равна 6 и граф связен, то, то 1 ≤ αi ≤ 4.
Теорема 2 Пусть Г – вполне регулярный граф с параметрами (32, 6, 0, 2) не может быть дистанционно регулярным.
Доказательство.
(1) 
Если каждая вершина из Г2(а) смежна с четырьмя вершинами из Г3(а) (т.е. αi = 4), то количество ребер выходящих из Г2(а) в Г3(а) равно 15·4 = 60. А так как степень графа Г равна 6 и, Г - а -[a] - Г2 (а) = 32 -1- 6 -15 =10 , то каждая из оставшихся 10 вершин лежит в Г3(а). Пусть Г3(а) = {c1, c2, c3, c4, c5, c6, c7, c8, c9, c10}. Заметим, что число рёбер между а и [a] равно 6, между [a] и Г2(а) равно 30, а между Г2(а) и Г3(а) равно 60. Всего же рёбер в графе Г равно 32·6/2 = 96. Таким образом, в Г3(а) ребер нет. Другими словами, каждое из множеств: а, [a], Г2(а), Г3(а) – коклики. Пусть теперь, вершина c1 смежна с вершинами b1, b2, b3, b4, b5, b6. Так как в Г3(а) рёбер нет, то вершины c1 и c2 не могут быть смежными, а так как μ(c1, c2) = 2, то в Г2(а) найдутся две вершины, смежные как с c1, так и c2. А так как [c1] = {b1, b2, b3, b4, b5, b6}, то μ(b1, b2) содержит вершины a1, c1 и c2. Противоречие.
2) Пусть каждая вершина из Г2(а) смежна с тремя вершинами из Г3(а) (т.е. αi = 3). Тогда Г2(а) граф степени 1, но тогда число вершин в Г2(а) должно быть чётным. Противоречие.
(3) Пусть каждая вершина из Г2(а) смежна с двумя вершинами из Г3(а) (т.е. αi = 2). Тогда Г2(а) – граф степени 2 на 15 вершинах. В этом случае, число рёбер в подграфе a È[a] È Г2 (a) равно 6 + 5·6+ 15·2 = 66. Между Г2(а) и Г3(а) ровно 15·2 = 30 рёбер. Так как всего рёбер в графе 96, то на оставшихся 10 вершинах рёбер нет. Каждая вершина из Г3(а) смежна с шестью вершинами из Г2(а). Но, число рёбер, выходящих из Г3(а) в Г2(а) равно 10·6 = 60. Следовательно, в Г3(а) не может быть 10 вершин.
(4) Пусть каждая вершина из Г2(а) смежна с единственной вершиной из оставшихся 10 (т.е. αi = 1). Тогда Г2(а) – граф, степени 3 на 15 вершинах. противоречие.
Список литературы
1. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs// Berlin etc: Springer-Verlag – 1989.
2. Махнёв А.А., Носов В.В. Об автоморфизмах графов с λ = 0, μ = 2. //Математический сборник. Том 195, №3, 2004, С. 47-68
