Расширения псевдогеометрических графов для $pG_{s-4} (s, t) $

Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a гра фа. Г через Г_i(a) обоз! шчим i-окрестиость вершины a. т. с.. подграф. индуцированный Г на. множестве всех вершин, находящихся на. расстоянии i от a. Подграф Г(a) = Г₁(a) называется опростиостью вершины a и обозиачается [a], если граф Г фиксирован. Положим a^± = {a} U [a].

Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени k. если степень лкибой вершины из Г равна. k. Г_Г>аф Г назовем реберно регулярным с параметрами (v, k, А), если он содержит v вершин, регулярен степени k. ii каждое его ребро лежит в А трсуголышпах. Граф Г - вполне регулярный граф с параметрами (v,k,A,^), если он реберно регулярен с соответствующими параметрами. ii [a] П [b] соле_Г>жпт д вершин для любых двух вершин a. b. находящихся на. расстоянии 2 в Г. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Пусть F - некоторый кла се графов. Граф Г назовем . вокально F-графом, если [a] лежнт в F для любой вершины a графа Г.

Если вершины u. w находятся на расстоянии i в Г. то ^юрез bi(u,w) (нерез ci(u,w) обозначим число вершин в пересечении Г_i+1(u) (Г^1 (u)) с [w]. Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {b₀, b1,..., b_d-1; а, ..., cd }, если значения bi(u,w) 11 ci(u,w) ио зависят от выбора вершин u. w на расстоянии i в Г для любого i = 0,... ,d. Положим ai = k - bi - ci.

Система инцидентности с множеством точек P и множеств ом прямых L называется а-частивной геомстрисй порядка (s,t) если каждая прямая содержит ровно s + 1 точку, каждая точка лежит ровно на t + 1 прямой, любые две точки лежат не более чем на одной прямой. II для любого антпфлага (a, l) Е (P, L ) найдете я точно а прямых, проходящих через a и пересекаюших l (обозначение pG_a(s,t)). В с.тучае а = 1 геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Точечный граф геометрии определяется на множестве точек P и две точки смежны, если они лежат на прямой. Точечный граф геометрии pG_a (s, t) сильно регулярен с v = (s + 1)(1 + st/а). k = s(t + 1).

• ¹    Работа выполнена при поддержке Министерства образования и пауки Российской Федерации, соглашение № 02.А03.21.0006 от 27.08.2013.

А = s — 1 + t(a — 1), ц = a(t + 1). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел a, s, t называется псевдогеометрическим грифом для ^pGa (s,t)

Дж. Кулен предложил задачу изучения дистанционно регулярных графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением 6 t для данного натурального числа t. Заметим, что сильно регулярный граф с нецелым собственным значением является графом в половинном случае, а вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы в половинном случае, либо имеет диаметр 2, либо является графом Тэйлора. Таким образом, задача Кулена сводится к описанию дистанционно регулярных графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением t для t = 1, 2,...

В [1] завершено решение задачи Кулена для t = 3. В работе [2] получена редукция задачи Кулена для t = 4 к случаю когда окрестности вершин — исключительные графы с неглавным собственным значением 4. В данной работе рассматриваются вполне регулярные графы, в которых окрестности вершин — псевдогеометрические графы для pGs-4(s,t).

Теорема 1. Пусть Г - вполне регулярный граф диаметра, большего 2. в котором окрестности вершин — псевдогеометрические графы для pG_s-4(s, t). Тогда выполняется одно из следующих утверждений:

• (1)    диаметр Г больше 3. .п юо s = 5 iit G {3, 5, 7}. niioo s = 6 iit = 1;

• (2)    d(r) = 3. niioo s = 8 п Г — граф Тэйлора, либо 5 6 s 6 7.

Теорема 2. Пусть Г — вполне регулярный граф, в котором окрестности вершин — пссвдогеомстрпчсскпс графы для GQ(5, t). t G {3, 5, 7,10,15,19, 20, 25}. Тогда верно одно из утверждений:

• (1)    Г - сидшю регулярный граф и либо

• (i)    t = 3 п Г имеет параметры (322, 96, 20, 32) пли (697, 96, 20,12). либо

  • (и) t = 5 ii Г имеет параметры (1782,156, 30,12) пли (532,156, 30, 52). либо

    (in) t = 7 ii Г имеет параметры (1792, 216,40, 24). либо

    (iv) t = 20 ii Г имеет параметры (2107, 606,105, 202);

• (2)    d(Г) = 3 л либо

• (1)    t = 3 11 ц G {6, 8, 9,10,12,15,16,18, 20, 25, 30, 32, 36,40,45,48, 50}. либо

• (и) t = 5 1 1 ц G {13,15, 20, 25, 26, 30, 39, 50, 52, 60, 65, 75, 78}. либо

• (ш) t = 7 1 1 ц G {25, 27, 28, 30, 35, 36,40,42,45, 50, 54, 56, 60, 63, 70, 72, 75, 84, 90,100, 105,108,120,126,135,140}. либо

(в-) t = 10 11 ц G {50, 60, 68, 90,100,102,150,170,180, 204}. либо

• ( л) t = 15 11 ц G {75,76, 90, 95,100,114,120,125,150,152,171,180,190,200,228, 250,285,300}. либо

• (VI) t = 19 11ц G {100,120,125,128,144,150,180,192, 200, 225, 240, 250, 256, 288,300, 360,375,384,400}. либо

фф t = 20 11 ц G {120,150, 200, 202, 250, 300, 404}. либо

• (viii) t = 25 iтц G {125,126,135,140,150,180,189, 210, 250, 252, 270, 300, 315, 350, 375, 378,420,450,500, 525, 540}:

• (3)    d(Г) > 3 i it G {3, 5, 7}.

Следствие. Пуств Г - дистанционно рогутярпый граф диаметра d > 3. в котором окрестности вершин — псевдогеометрические графы для pG_s-4(s,t). Тогда верно одно из утверждений:

• (1)    s = 8 п Г — грае}) Тэйлора:

• (2)    s = 6,t = 1 и Г - половинный 8-куб:

• (3)    s = 5 и .аюо t = 1 и Г - граф Джонсона J(12, 6) или его стандартное частное, либо t = 3 и Г - граф с массив ом пересечений {96, 75,16,1; 1,16, 75, 96} иа 644 вершинах.

• 2. Вполне регулярные локально псевдо pGs-4(s, <)-графы

Лемма 1. Пуств Г - псевдогеометр!шыжпй граф для pG_s-4(s,t). А - регулярный подграф степени (s — 4)(t + 1) н aw вершинах. Тогда выполняются следующие утверждения:

• (1)    v(st — 4t + s — 8)/(st + s — 4) 6 w 6 (s — 3)v/(s + 1), если одно из этих нестрогих неравенств превращается в равенство, то любая вершина из Г — А смежна с 4(t + 1)w/(v — w) вершинами из А;

• (2)    ее. ш Xi - множеств о вершин из Г — А. смежных точно с i вершинамп из А. xi = |Xi|. то (2st + 2s + t — 3)2 w • xo 6 (v — w)(v — xo)(t + 5)2;

• (3)    ec.in w = xo. то 2(st + t + s + 1)xo 6 v(t + 5).

C Ввиду [3] верпы неравенства —(t + 1) 6 (s — 4)(t + 1) — 4(t + 1)w/(v — w) 6 4.

Отсюда v(st — 4t + s — 8)/(st + s — 4) 6 w 6 (s — 3)v/(s + 1). Если одно из этих нестрогих неравенств превращается в равенство, то ввиду [3] любая вершина из Г — А снежна точно с 4(t + 1)w/(v — w) вершинами из А.

По предложению 4.6.1 из [4] имеем w -xo 6 (v—w)(v—x_o)(t+5)2 /(2s(t +1)—4+(t+1))². Поэтому (2st + 2s + t — 3)2 w • xo 6 (v — w)(v — xo)(t + 5)2.

Если w = xo. т о (2st + 2s + t — 3)xo 6 (v — xo)(t + 5). поэтому (2st + 2s + 2t + 2)xo 6 v(t + 5). B

Лемма 2. Если диаметр Г бодыле 3. то . тпбо s = 5 iit G {3, 5, 7}. .и юо s = 6 iit = 1.

C Пу<-ть Г содержит геоде::отческий 4-путь u w. x. y. z. Тогда в графе [x] между [u] П [x] и [x] П [z] нет ребер ii ввиду леммы 1 имеем v(st — 4t + s — 8)/(st + s — 4) 6 w 6 v(t + 5)/(2st + 2s + 2t + 2). Поэтому 2(st + s + t + 1)(st — 4t + s — 8) 6 (st + s — 4)(t + 5).

В слтнае s = 5 имеем 12(t+1)(t—3) 6 (5t+1)(t+5). поэ тому t 6 7. Ввиду предложения t Л³,^{5 7}}-                .........

В случае s = 6 имеем 14(t + 1)2(t — 1) 6 2(3t + 1)(t + 5). поэтому t 6 2. Так как псевдогеометрнческий граф для pG2(6, 2) не является псключ!стольным графом. то t = 1.

В случае s = 7 имеем 16(t + 1)4t 6 4(2t — 1)(t + 5). противорсчпс. B

Лемма 3. Если диаметр Г равен 3. то .тпбо s = 8 п Г - граф Тэйлора, либо 5 6 s 6 7.

C Ее ли s = 8. то Г - граф Тэйлора.

Пусть s = 8. Тогда k = v⁰ = (s + 1)(1 + st/(s — 4)), А = k⁰ = s(t + 1) и b1 = 5st/(s — 4). Ввиду леммы 1 имеем (s + 1)(1 + st/(s — 4))(st — 4t + s — 8)/(st + s — 4) < 5st/(s — 4). поэтому (s + 1)(st — 4t + s — 8) < 5st. Отсюда s 6 7. Лемма, а вместе с ней ii теорема 1 доказаивк B

Лемма 4. Пусть u, w — вершины из Г с d(u, w) = 2. Тогда выполняются следующие утверждения:

• (1)    6(t - 3) 6 ц 6 5ft + l⁾(5t ₊ l^)/(t + 3); _

• (2)    ее. тп Xi — множеств о вершин ne; [w] — [u]. смежных точно с i вершшнаш in [u] П [w]. Xi = |Xi|. то xo • ц 6 (v⁰ — xo)(v⁰ — ц)(t + 5)2/(11t + 7)2;

• (3)    ее.ш xo = ц. то ц 6 (t + 5)(5t + 1)/(2t + 2).

C Ввиду леммы 1 в(?риы неравенства —(t + 1) 6 (t + 1) — 4(t + 1)ц/(30t + 6 — ц) 6 4.

Отсюда 6(t — 3) 6 ц 6 5(t + 1)(5t + 1)/(t + 3). Если одно из этих нестрогих неравенств превращается в равенство, то любая вершина из [w] — [u] П [w] смежна точно с 4(t + 1)ц/(30t + 6 — ц) вершинами из [u] П [w].

Имеем ц • x_o 6 (v⁰ — ц)(у' — x_o)(t + 5)2/(10(t + 1) — 4 + (t + 1))². Поэтому x_o • ц 6 (v⁰ — Xo )(v⁰ — ц)(t + 5)2/(11t + 7)2.

Если xo = ц. т о (11t + 7)ц 6 (30t + 6 — ц)(t + 5). поэтому ц 6 (t + 5)(5t + 1)/(2t + 2). B

Лемма 5. Если Г - сильно регуляршяП локалвпо псевдо GQ(5,t)-rpa4>. то верно одно из утверждений:

• (1)    t = 3 и Г имеет параметра! (322,96, 20, 32) или (697, 96, 20,12):

• (2)    t = 5 ii Г имеет параметры (1782,156, 30,12) или (532,156, 30, 52):

• (3)    t = 7 и Г имеет параметры (1792, 216,40, 24):

• (4)    t = 20 11 Г имеет параметры (2107, 606,105, 202).

C Пу< mb (v⁰,k⁰,A0,ц⁰) - парамотры псевдо GQ(5,t)-rpaa 11 Г имеет неглавные собственные значения n — m, —m. Тогда m — 1 де.тит v⁰ — k⁰ — 1 = 25t. Далее, m > t + 1. n — m = 25t/(m — 1) — 1 1 in — m > 4. поэтому m — 1 6 5t.

В случае параметров (96, 20,4,4) hikmo m — 1 делит 75. поэтому m — 1 = 5,15. соответственно n — m =14,4. Г имеет параметра! (697, 96, 20,12) пли (322, 96, 20, 32) ii заключение леммы выполняется.

В случае параметров (156, 30,4, 6) чшмо m — 1 делит 125. поэтому m — 1 = 5, 25. соответственно n — m = 24,4 11 Г имеет параметра! (1782,156, 30,12) пли (532,156, 30, 52) и заключение леммы выполняется.

В случае параметров (216,40,4, 8) чшмо m — 1 делит 175. поэтому m — 1 = 5, 7, 25, 35. соответственно n — m = 34, 24, 6,4. Г имеет параметры (v, 216,40,12). (v, 216,40, 24). (v, 216,40, 60) пли (v, 216,40, 72). Во всех случаях, кроме второго, кратности n — m не целая, поэтому заключение леммы выполняется.

В случае параметров (306, 55,4,11) hikmo m—1 делит 250. поэтому m—1 = 5,10, 25, 50. соответственно n — m = 49, 24, 9,4 11 Г имеет параметры (v, 306, 55,12). (v, 306, 55,42). (v, 306, 55, 72) пли (v, 306, 55,102). Так как ц дел нт 306 • 250. то ц = 12,102. В обоих случаях кратности n — m не целая, противоречие.

В случае параметров (450, 80,4,16) hikmo m — 1 делит 375. поэтому m — 1 = 15, 25, 75. соответственно n — m = 24,14,4. Г имеет параметры (v, 450, 80, 66). (v, 450, 80, 86) пли (v, 450, 80,146). Протпворечне с тем. что ц не д<мнт 450 • 375.

В случае параметров (576,100,4,20) чшмо m — 1 делит 19 • 25 = 475. поэтому m — 1 = 19, 25, 95. соответственно n — m = 24,18,4. Г имеет параметры (v, 576,100, 90). (v, 576,100,102) или (v, 576,100,186). Так как ц дел нт 576 • 475. т о ц = 90. противоречие с тем. что кратности 24 равна 19 • 576 • 596/(44 • 90).

В случае параметров (606,105,4,21) hik:mo m — 1 делит 500. поэтому m — 1 = 20, 25, 50,100. соответственно n — m = 24,19,9,4. Г имеет параметры (v, 606,105,102). (v, 606,105,112). (v, 606,105,147) пли (v, 606,105, 202). Taiс как ц дел нт 606 • 500. то ц = 202.

В случае параметров (756,130,4,26) чиело m — 1 делит 25 • 25 = 625, поэтому m — 1 = 25,125. соответствешю n — m = 24,4. Г имеет параметры (v, 756,130,132) пли (v, 756,130, 252). Так как р дел нт 756 • 625. т о р = 252. противоречие с тем. что кратными 4 равна 125 • 756 • 882/(130 • 252). B

До конца параграфа будем предполагать, что диаметр Г больше 2. Заметим, что каждый р-подграф регулярен степени t + 1. поэтому в елучае четного t параметр р четен.

Лемма 6. Если t = 3. то верны следующие утверждения:

• (1)    р € {6, 8, 9,10,12,15,16,18, 20, 25,30, 32, 36,40, 45,48, 50):

• (2)    если диаметр Г болвше 3. то р 6 16.

C В случае параметров (96, 20,4,4) по лемме 6 имеем 0 < р < 20 • 16/6. поэтому 5 < р< 53. Так как р дед пт 96 • 75. то р € {6, 8, 9,10,12,15,16,18, 20, 25, 30, 32, 36,40,45, 48,50^}.               _            _                                     _

Если диаметр Г иолыле о. то ввиду утверяедения (о) леммы 6 имеем р 6 8 • 16/8. поэтому р 6 16. B

Аналогично доказываются следующие две леммы.

Лемма 7. Если t = 5. то верны следующие утверждения:

• (1)    р € {13,15, 20, 25, 26, 30, 39, 50, 52, 60, 65, 75, 78};

• (2)    если диаметр Г болыне 3. то р € {13,15, 20}.

Лемма 8. Если t = 7. то верив! следующие утверждения:

(1)р € {25,27,28, 30, 35, 36,40,42,45, 50, 54, 56, 60, 63, 70, 72, 75, 84, 90,100,105,108,120,

126,135,140);          _                        .       _

• (2)    если диаметр Г оодвше 3. то р € {25, 27).

Лемма 9. Пуств t > 7. Тогда диаметр Г равен 3 и верив! следующие утверждения:

• (1)    ее.тп t = 10. то р € {50, 60, 68, 90,100,102,150,170,180, 204);

• (2)    ее.тп t = 15. то р € {75, 76, 90, 95,100,114,120,125,150,152,171,180,190, 200, 228, 250, 285, 300};

• (3)    ее.тп t = 19. то р € {100,114,120,144,150,152,160,171,180,190,192, 200, 225, 228, 240, 250, 285, 288, 300, 304, 320, 342, 360, 380, 400};

• (4)    ее.тп t = 20. то р € {120,150, 200, 202, 250, 300,404):

• (5)    ее.тп t = 25. то р € {125,126,135,140,150,180,189, 210, 250, 252, 270, 300, 315, 350, 375,378,420,450, 500, 525, 540).

C Ес ли t > 10. то нарушается неравенство 6(t — 3) 6 р 6 (t + 5)(5t + 1)/(2t + 2). поэтому диаметр Г равен 3.

В случае параметров (306, 55,4,11) имеем 42 < р < 55 • 51/13. поэтому 42 < р < 216. _{Так как} р делиг 306 • 250. т„ р ^{€ {50},60,68,90,100,102,150,170,180,20Д

В случае параметров (456,80,4,16) имеем 72 < р < 80 • 76/18. поэтому 72 < р < 338. Так как р лея пт 456 • 15 • 25. т о р € {75, 76, 90, 95,100,114,120,125,150,152, 171,180,190,200,228, 250,285,300⁾.

В случае параметров (576,100,4,20) имеем 96 < р < 100^96/22. поэтому 96 < р < 437. Так как р дел пт 576 • 475. т о р € {100,114,120,144,150,152,160,171,180,190,192, 200, 225,228,240,250, 285, 288, 300,304,320,342,360,380,400).

В случае параметров (606,105,4,21) имеем 102 < р < 105 • 101/23. поэтому 102 < р < 461 Тж _Юк р л, ллл 606 • 500. л<. р ^{€ {}120,150,200,202,250,300,⁴⁰⁴⁾.

В случае параметров (756,130,4,26) имеем 132 < р < 130 • 126/28. поэтому 132 < р < 585. Так как р лед пт 756^625. то р € {125,126,135,140,150,180,189, 210, 250, 252, 270, 300, 315, 350,375,378,420, 450,500,525, М0).

B

• 2. Дистанционно регулярные локально псевдо pGs-4(s, !)-графы

В этом параграфе предполагается, что Г - дистанционно регулярный граф диаметра d > 3. в котором окрестности вершин - пеевдогеометрнчеекне графы для pGs_-4(s,t). Пусть 90 >91 > ...>9_d- собственные зпаления шрафа Г. Зафпкспру ем вершину u Е Г к положим ki = |ri(u)|.

Лемма 10. Если d > 4. то верно онио из утверждений:

• (1)    s = 5 п Г - граф с лассивол пересечений {96, 75,16,1; 1,16, 75, 96} иа 644 вершинах;

• (2)    s = 6 п Г - половинный 8-куб.

C Пусть днаметр Г больше 3 11 и. w. x.y. z- теолезпче скин путь в Г. В елучае s = 6 по лемме 2 имеем t = 1 п 28р 6 28 • 6. поэтому р = 6 11 р-подгр;к]>ы в Г - октаэдры. Палее, для вершины и Е Г граф А = [и] - трсуго.льиын граф T (8). В этом случае Г -половинный 8-куб.

Если s = 5. то по ломею 1 имеем t Е {3, 5, 7} 11 6(t - 3) 6 р 6 2(5t + 1).

В случае t = 3 нмсм р 6 32 п Г является .тока.тыю псевдо GQ(5, 3)-графом. Ввиду теоремы из [7] выполняется заключение леммы.

В случае t = 5 имеем 12 6 р 6 52. Так как р дел нт 156 • 125. т о р Е {13,15, 20, 21, 25, 26, 30, 39, 50}. Да лее, 61 = 125, по теореме Тервиллигера [8, теорема 4.4.3] выполняются неравенства. -6 >  6— = -1 - 61/(91 + 1). 4 6 6+ = -1 - 61/(9_d + 1). Поэтому 91 6 24 ii 9_d > -26. Компьютерные вычне.тения показывают, что 91 > 34. противоречие.

В случае t = 7 имеем 24 6 р 6 72. Так как р дел нт 6 • 36 • 175. т о р Е {25, 28, 30, 35, 36, 40,42,45, 50, 54, 56, 60, 63, 70}. Да лее, 61 = 175, по теореме Тервиллигера [8, теорема 4.4.3] выполняются неравенства. -8 >  6— = -1 - 61/(91 + 1). 4 6 6+ = -1 - 61/(9_d + 1). Поэтому 91 6 24 11 9_d > -36. В любом с.тучае имеем 91 > 44. противорсчис. в

Лемма 11. Если d = 3 и s = 6, то граф Г не является дистанционно регулярным.

C Пусть л памстр Г равен 3. Ес-ли s = 6. то по лемме 1 имеем 7(t - 1) < р< 3(3t + 1) и t ^Е {1,5, 7,9,10,15,16, 23,25,30,37^}. Да.w. k = 7(1 + ЭД. 6, = 151. р ^ _m Ю^¹ + St) и р-подграфы регулярны степени 2(t + 1). По теореме Тервиллигера [8, теорема 4.4.3] выполняются неравенства, -(t + 1) > b^- = -1 - 61/(91 + 1). 4 6 6+ = -1 - 61/(9_d + 1). Поэтому 91 6 14 11 9_d >  -(3t + 1).

Если t = 1. то 5 6 р 6 12. В этом случае р Е {6, 7,10}. Пэ-сть р = 6. Тогда 62 четно. k₂ = 70 11 c₃ де. лит 7062. Пэ-сть р = 7. То гда 62 делите я на. 7. k₂ = 60 11 c₃ де. лит 6062. Пусть р = 10. То гда 62 чет но. k₂ = 42 11 c₃ де. тит 4262. В любом случае допустимых массивов пересечений нет.

Если t = 5. то 28 6 р 6 48. В этом случае р Е {30, 35,40,42} 11 9_d > -16. Пусть р = 30. То гда 62 чет но. k₂ = 280 11 c₃ де. лит 28 062. Пэ-сть р = 35. То гда 62 делится на. 7. k₂ = 240 11 c₃ де. лит 24062. Пэ-сть р = 40. То гда 62 делите я на. 8. k₂ = 210 11 c₃ делит 2 1062. Пэ-сть р = 42. Тогда 62 делитсяi на. 14. k₂ = 200 11 c₃ де.лит 20062. В любом случае 91 > 15. противоречие.

Если t = 7. то 42 6 р 6 66. В этом случае р Е {49, 55}. Пэ-сть р = 49. Тогда 62 делится на. 7. k₂ = 330 11 c₃ де.лит 33062. Пэ-сть р = 55. Тогда 62 делитмi на. 11. k₂ = 294 ii c₃ де.тит 29462. В любом случае 91 > 18. противоречие.

Если t = 9. то 56 6 р 6 84. В этом случае р Е {60, 63, 70}. Пэ-сть р = 60. Тогда 62 делится на. 4. k₂ = 441 11 c₃ де. тит 44162. Пэ-сть р = 63. То гда 62 делите я на. 7. k₂ = 420 ii c₃ де.тит 42062. Пэ-сть р = 70. Тогда 62 делитмi на. 14. k₂ = 378 11 c₃ де.лит 37862. В любом случае 91 > 18. противоречие.

Если t = 10. то 63 6 р 6 93. В этол случае р Е {70, 75} 11 9d > -31. Пэ ( ть р = 70. Тогда b₂ делите я на. 7. k₂ = 465. c₃ де. тит 465b2 11 91 > 14. Пэ-сть р = 75. Тогда к₂ = 434 я с₃ де.тит 434b2. В этол случае либо 91 > 14. Л1 ибо Ь1 6 2. В любом случае допустимых массивов пересечений нет.

Если t = 15. то 98 6 р 6 138. В этоэi случае р Е {105,115} 11 9_d > -46. Пусть р = 105. То гда b₂ делите я на. 7. к₂ = 690. с₃ де. тит 690b2 11 91 > 24. Пэ-сть р = 115. Тогда b₂ делится на. 23. к₂ = 630 11 91 > 34.

Если t = 16. то 105 6 р 6 147. В этол случае р Е {112,120,140} 11 9_d > -49. Пусть р = 112. То гда b₂ делите я на. 7. к₂ = 735. с₃ де. тит 735b2 11 91 > 24. Пэ-сть р = 120. Тогда к₂ = 686 11 с₃ дс, ни 686b2. В этол с. тучае либо 91 > 14. .и 160 Ь1 6 2. Пэ-сть р = 140. Тогда b₂ делите я на. 7. к₂ = 588. с₃ де. тит 588b2 11 91 > 17. В любом случае допустимых массивов пересечений нет.

Если t = 23. то 154 6 р 6 210. В этоэi случае р Е {161,175} 11 9_d > -70. Пусть р = 161. То гда b₂ делите я на. 7. к₂ = 1050 11 c₃ делит 1050b2. В этоэ i случае 91 >  28. Пусть р = 175. Тогда b₂ делится на. 36 и 91 >  49.

Если t = 25. то 168 6 р 6 228. В этом случае р Е {175,190, 210} 11 9_d > -76. Пусть р = 175. То гда b₂ делите я на. 7. к₂ = 1140 11 c₃ дел ит 1140b2. В этоэ i случае 91 >  28. Пэ-сть р = 190. Тогла b₂ делится на. 38 и 91 >  38. Пэ-сть р = 210. Тогла b₂ делится на. 14 ¹¹°1 > ²8

Если t = 30. то 203 6 р 6 273. В этом случае р Е {175,190, 260} 1i 9d > -76. Пусть р = 175. То гда b₂ делите я на. 7. к₂ = 1140 11 c₃ дел ит 1140b2. В этоэ i случае 91 >  45. Пусть р = 190. Тогда b₂ делится на. 38 и 91 >  70. Пэ-сть р = 210. Тогда b₂ делится на. 14 я 91 >  41.

Если t = 37. то 252 6 р 6 336. В этом случае р Е {259, 280, 294, 296} 11 9_d > -112. Пусть р = 259. То гда b₂ делите я на. 7. к₂ = 1680 11 c₃ дел ит 1680b2. В этом случае 91 >  32. Пусть р = 280. Тогда b₂ делится на. 66 и 91 >  75. Пэ-сть р = 294. Тогда b₂ делится на. 98 я 91 >  92. Пэ-сть р = 296. Тогда b₂ делится на. 8 и 91 > 25. B

Лемма 12. Если d = 3 ns = 7, то граф Г не является дистанционно регулярным.

C Пэ-сть лпамстр Г равен 3. Е(эти s = 7. то по лемме 1 имеем 8(3t - 1)/3 6 р <  ⁴(7t/3 ₊ 1) .. t ^Е {9,15,27,30,51,75). Д„л», k = 8(^7t/3 + 1). b, = 3^5t/3 + 1. р .г» 8(7 t/ 3 + 1)(35 t/ 3 + 1) µ 3( t + 1)

[8, теорема 4.4.3] выполняются неравенства -(t + 1) >  b- = -1 - b1/(91 + 1), 4 6 b+ = -1 - ₆₁/(»d ⁺ 1). П.»W 01 ⁶ (^35t/3 + IVt ^- 1 ,Md > -((351/3 ⁺ 1^)/5 + 1).

Если t = 9, to 70 6 р <  88. В этом случае р делит 32 • 11 • 53, противоречие. Если t = 15. то 118 6 р < 144. В этом случае р Е {128,132}. 91 6 161/15 11 9_d > -181/5. Пусть р = 128. То гда b₂ делите я на. 8. к₂ = 396 11 c₃ де. тит 396b2. В этом случае 91 >  23. Пусть р = 132. Тогда b₂ делится на. 3 и 91 >  14.

Если t = 27. то 214 6 р< 256. В этом случае р делит 79 • 2048. противоречие. Если t = 30. то 238 6 р < 287. В этом случае р делит 8 • 27 • 13 • 71. противор<-пю. Если t = 51. то 406 6 р < 480. В этом случае р = 447. 91 6 545/51 11 9_d > -601/5. Да,лее. b₂ делится на. 3. к₂ = 1280 11 c₃ делит 1280b2. В этом случае 91 >  17.

Если t = 75. то 598 6 р< 704. В этом случае р делит 512 • 11 • 219. противорсчпс. в

Пусть до конца работы s = 5.

Лемма 13. Если 5 6 t 6 10, то граф Г не является дистанционно регулярным.

C Пусть t = 5. Тогда по теореме Тервиллигера [8, теорема 4.4.3] выполняются неравенства. -4 >  b- = -1 - Ь1 /(91 + 1). 3 6 b+ = -1 - b1/(9_d + 1). Поэтому 91 6 24 н 93 > -26.

Если ц = 13. т о b2 делится на. 13 и 61 >  24. противорс'лие. Если ц = 15. т о b2 делится на 3 и либо 61 >  24, либо с₃ >  144. В любом случае допустимых массивов пересечений нет.

Если ц = 20. то b₂ делится игс 4 и либо 61 >  24. .иi6o с₃ >  138. В любом случае допустимых массивов пересечений нет. Если ц = 25, при b₂ = 18, с₃ = 148 имеем 61 >  24 II 63 <  -26. противореча 10. Поэтому b₂ 6 17. В любом случае допустимых массивов пересечений нет.

Если ц = 26. то b₂ делится на. 26 и либо 61 >  24. .иибо b₂ = 26 11 с₃ = 155,156. В любом случае допустимых массивов пересечений нет. Если ц = 30, то b₂ делится на 6 и либо 61 >  24, либо с₃ >  136. В любом случае допустимых массивов пересечений нет.

Если ц = 39. то b₂ делится на. 39. противоречие. Если ц = 50. то при b₂ = 2,с₃ = 131 имеем 61 >  24 11 63 <  -26. противорс-шс. Если ц = 52. то b₂ делится на. 62. противоречие.

Если ц = 60. то b₂ делится и;с 12 и при b₂ = 12, с₃ = 130 шк?ем 61 >  24 11 63 <  -26. противоречие. Если ц = 65. то b₂ делится и а. 13 и при b₂ = 13,с₃ = 130 имем 61 >  24 и 63 <  -26. противорс -чис. Если ц = 75. то b₂ делится и а. 3 и при b₂ = 3,с₃ = 130 имеем 61 >  24 11 63 <  -26. противорс-чис. Если ц = 78. то b₂ делится на. 78. противоречие.

Птетв t = 7. Тогда по теореме Тервиллигера выполняются неравенства 61 6 24 п ⁶d > ^-36           .....

Если ц = 25, то либо 61 > 24, либо bi = 1,с₃ = 216 и некоторое собственное значение имеет нецелую кратность, противоречие. Если ц = 27, то b₂ делится на 27 и 61 > 24. противорс чис. Если ц = 28. то . тибо 61 >  24. hi ибо b1 = 4, с₃ = 216 и некоторое собственное значение имеет нецелую кратность, противоречие. Если ц = 30, то либо 61 >  24, либо b1 = 6,с₃ = 216 и некоторое собственное значение имеет нецелую кратность, противоречие.

Если ц = 35. то .тибо 61 >  24. hi 160 с₃ >  195. В любом случае допустимых массивов пересечений нет, противоречие.

Если ц Е {36,54,72,108}. то b₂ делится на. ц. противоречие. Если ц Е {40,45, 60, 90,120,135}. то b₂ делится на ц/5 и допустимых массивов пересечений нет. противоречие. Если ц Е {42, 56, 63, 84,126}. то b₂ делится на. ц/7 п допустимых массивов пересечений нет, противоречие.

Если ц = 50. то b₂ делится игс 2 ii либо 61 >  24. hi 160 с₃ > 194. В любом случае допустимых массивов пересечений нет, противоречие. Если ц = 70, то b₂ делится на 2 и либо 61 >  24, либо с₃ > 194. В любом случае допустимых массивов пересечений нет, противоречие.

Аналогично рассматриваются оставшиеся значения ц Е {75,100,105,140}.

Птетв t = 10. Тогда по теореме Тервиллигера выполняются неравенства 61 6 24 п ⁶d >^-5L

Если ц = 50, то л ибо 61 > 24, ли бо сз > 288. В любом случае допустимых массивов пересечений нет, противоречие. Если ц = 60, то b₂ делится на 3 и либо 61 >  24, либо с₃ > 289. В любом случае допустимых массивов пересечений нет, противоречие.

Если ц = 68. то b₂ делится на. 34 п 61 >  24. противорсмне. Если ц = 90. то b₂ делится на. 9 ii при b₂ =9. с₃ = 289 имем 61 >  24 11 63 <  -51. противорс-ше. Если ц = 100. то b₂ делится ii а. 2 п при b₂ = 2. с₃ = 280 нмем 61 >  24 11 63 <  -51. противоречие. Если ц = 102. то b₂ делится на. 61. противоречие.

Если ц = 150. то b₂ делится иа. 3 и при b₂ = 3. с₃ = 280 нмем 61 >  24 11 63 <  -51. противоречие. Если ц = 170. то b₂ делится и;с 17 и при b₂ = 3. с₃ = 280 нмем 61 >  24 п 63 <  -51. противорс-ше. Если ц = 180. то b₂ делится иа. 18 и при b₂ = 3. с₃ = 280 имеем 61 >  24 11 63 <  -51. противорс-ше. Если ц = 204. то b₂ делится на. 102. противоречие. B

Лемма 14. Если 15 6 t 6 25, то граф Г не является дистанционно регулярным.

<1 Пл-отв t = 15. Тогда по теореме Тервидлигера выполняются неравенства 91 6 24 и ⁶d > — ⁷⁶'

Если ц = 75, то либо 91 >  24, либо Ь₂ = 1, С3 = 456 и некоторое собственное значение имеет нецелую кратность, противоречие. Если ц = 76, то b₂ делится на 76, противоречие.

Если ц = 90. т о b₂ делится iia. 6. либо 91 >  24. hi вбо b₂ = 1,c₃ = 456 и некоторое собственное значение имеет нецелую кратность, противоречие. Если ц = 95, то b₂ делится на. 19 ii 91 >  24. Ес ли ц = 100. т о b₂ делится иа. 4 и либо 91 >  24. hi i6o c₃ >  443. В любом случае допустимых массивов пересечений нет, противоречие.

Если ц = 114. то b₂ делится на. 38. противорение. Если ц = 120. то b₂ делится на. 8 и либо 91 >  24, либо С₃ > 444. В любом случае допустимых массивов пересечений нет, противоречие.

Если ц = 125. то .либо 91 >  24. hii6o c₃ > 434. В любом случае допустимых массивов пересечений нет, противоречие. Если ц = 150, то b₂ делится на 2 и при b₂ =2, c₃ = 433 имеем 91 >  24 и 93 <  -76, противоречие. Аналогичное противоречие получится и для оставшихся ц € {152, 171, 180, 190, 200, 228, 250, 285, 300}.

Пуств t = 19. Тогда по теореме Тервиллигера выполняются неравенства 91 6 24 и ⁹d > —⁹⁶'                ,                                       .      .

Если ц = 100, то b2 делится на 4, а если ц = 114, то b2 делится на 6. В любом случае 91 >  24. противоречие. Аналогичное противоречие получится при ц Е {120,144, 160,18°, 192^}.

Если ц = 152. т о b2 делится iia. 8. лноо 91 > 24. hiioo c3 > 566. В люоом случае допустимых массивов пересечений нет, противоречие. Если ц = 171, то b₂ делится на 9, либо 91 >  24, либо c₃ > 564. В любом случае допустимых массивов пересечений нет, противоречие.

Если ц = 190. то b₂ делится иа. 2 и при b₂ = 2,c₃ = 554 имем 91 >  24 11 93 <  -96. противоречие. Аналогичное противоречие получится при оставшихся ц Е {200, 225, 228, >50, 285,288, 3⁰⁰, ³⁰4, 320,342,³⁶0,380,^400}.

Пуств t = 20. Тогда по теореме Тервиллигера выполняются неравенства 91 6 24 и ⁹d >-¹°¹■            .

Если ц = 120. т о b2 делитсяi на. 6 п 91 > 24. противорсмне. Если ц = 150. т о b2 делится на 3 и либо 91 >  24, либо c₃ > 589. В любом случае допустимых массивов пересечений нет, противоречие.

Если ц = 200. то b₂ делится иа. 2 п при b₂ = 2, c₃ = 584 имем 91 >  24 11 93 <  -101. противоречие. Если ц Е {202,404}. то b₂ делится на. 101. п_Гютиворечие. Если ц = 250. то при b₂ = 1,c₃ = 580 имем 91 >  24 11 93 <  -101. противорс-чис. Если ц = 300. т о b₂ делится на. 3 и при b₂ = 3, c₃ = 580 нмем 91 >  24 11 93 <  -101. противоречие.

Пуств t = 25. Тогда по теореме Тервиллигера выполняются неравенства 91 6 24 п »d >  -126.

Если ц = 125. т о 91 >  24. противорс'ние. Если ц не делится на о. то b2 делится на. ц/4. ц/2 ii. ти ц. противоречие. Если ц не делится на. 26. то (b₂,ц) делит■ 20 п 91 >  24. противоречие.

Если ц = 150. то b₂ делится шi 3 ii либо 91 >  24. hii6o c₃ > 754. В любом случае допустимых массивов пересечений нет, противоречие. Если ц = 250, то либо 91 >  24, либо b₂ = 1,c3 >  734. В любом случае допустимых массивов пересечений нет, противоречие. Если ц = 300. то b₂ делится иа. 3 и при b₂ = 3. c₃ = 734 имем 91 >  24 и 93 <  -126, противоречие. Аналогичное противоречие получится при оставшихся ц Е {350, 375,450, 500, 525}. .Темма, п следелвие доказаны, в