Расширения псевдогеометрических графов для pGs-5 (s, t)

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

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

Если вершины u. w находятся на расстоянии i в Г. то нсрез bi(u,w) (нерез ci(u,w) обозначим число вершин в пересечении Г_i+1(u) (Г_i-1(u)) с [w]. Граф Г диаметра d называется дистанционно регулярным с массивом пересечении {b₀, b1,..., b_d-1; c1, ..., 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 и две точки смежны, если они лежат на прямой. Точечный гра4> геометрии pG_a (s, t) сильно регулярен с v = (s +1)(1 + st/а). k = s(t + 1). А = s - 1 + t(a - 1), д = а(t + 1). Сильно регулярный граф с такими параметрами

• ¹    Работа выполнена при поддержке гранта Российского научного фонда, проект № 15-11-10025 (теорема 1 и следствие), а также соглашения между Министерством образования и пауки Российской Федерации и Уральским федеральным университетом от 27.08.2013, № 02. А03.21.0006 (теорема 2).

для некоторых натуральных чисел a, s, t называется псевдогеометрическим графом для pGa (s,t)

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

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

В данной работе рассматриваются дистанционно регулярные графы, в которых окрестности вершин — исключительные псевдогеометрические графы для pGs-5(s,t). Выделим сначала параметры (s,t) которые имеет исключительный псевдогеометриче-ский граф для pGs_-5(s,t), вкладываемый в качестве окрестности вершины в дистанционно регулярный граф.

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

• (1)    (6, 3), (6,4), (6, 6), (6, 8), (6, 9), (6,12), (6,14), (6,15), (6, 22), (6,24), (6, 29), (6, 30), (6,36);

• (2)    (7,1), (7,4), (7, 6), (7, 8), (7, 9), (7,14), (7,15), (7,18), (7, 22), (7,24), (7, 29), (7, 34), (7, 36), (7, 50), (7, 54);

• (3)    (8, 2), (8,4), (8, 6), (8, 9), (8,10), (8,12), (8,14), (8,18), (8, 24), (8, 30), (8, 34), (8, 39), (8,42), (8, 54), (8, 66), (8, 74), (8, 84);

• (4)    (9,12), (9, 24), (9,44), (9,48), (9, 84), (9,144), (10,4), (10,16), (10, 24), (10, 27), (10, 38), (10,49), (10, 54), (10, 60), (10,104), (10,126), (10,159), (10, 214).

Теорема 1. Пусть Г - вполне регутяривш граф диаметра, большего 2. в котором окрестности вершин — исключительные псевдогеометрические графы для pG_s-5(s,t). Если диаметр Г больше 3. то . тпбо s = 6 iit Е {3,4, 6, 8, 9}. mii6o s = 7 iit = 1. Если же диаметр Г равен 3, то либо s = 10 и Г - граф Тэйлора, либо выполняется одно из следующих утверждений:

• (1)    s = 9, t = 12 ii 118 6 р 6 162;

• (2)    6 6 s 6 8.

Теорема 2. Пусть Г - вполне регутяривш граф диаметра 3. в котором окрестности вершин - псевдогеометрпческпе графы для GQ(6, t). t Е {3,4, 6, 9,12,14,15, 22, 24, 29, 30, 36}. Тогда верно одно из утверждений:

• (1)    t = 3. р Е {6, 7, 9,12,14,18,19, 21, 24, 27, 28, 36, 38,42, 54, 57, 63, 76, 84};

• (2)    t = 4. р Е {6, 8,10,12,14,16,18, 20, 24, 28, 30, 36, 40,42,48, 50, 56, 60, 70,

• 72,    80, 84, 90, 100, 112, 120, 126, 140};

• (3)    t = 6. р Е {18, 24, 28, 36,42, 54, 56, 72, 74, 50, 84,108,126,148,168};

• (4)    t = 8. р Е {32, 36,42,48, 54, 56, 72, 84, 96, 98,112,126,144,168,196, 224, 252};

• (5)    t = 9. р Е {36 , 42 , 44 , 45 , 54 , 55 , 60 , 63 , 66 , 70 , 77 , 81 , 84 , 90 , 99 , 105 , 108 , 110 , 126 , 132 , 140 , 154 , 162 , 165 , 189 , 198 , 210 , 220 , 231 , 252 , 264 , 270 , 297 , 308 , 315};

• (6)    t = 12. р Е {72 , 84 , 108 , 112 , 126 , 144 , 146 , 168 , 216 , 252 , 292 , 336 , 378};

• (7)    t = 14. р Е {72 , 84 , 90 , 102 , 118 , 120 , 126 , 136 , 140 , 168 , 170 , 180 , 196 , 204 , 210 , 238 , 252 , 280 , 294 , 306 , 360 , 392 , 408 , 420 , 476 , 490};

• (8)    t = 15. р Е {78 , 84 , 90 , 91 , 98 , 105 , 108 , 117 , 126 , 130 , 140 , 135 , 147 , 156 , 180 , 182 , 189 , 195 , 196 , 210 , 234 , 245 , 252 , 260 , 270 , 273 , 294 , 315 , 351 , 364 , 378 , 420 , 441 , 455 , 490 , 510 , };

• (9)    t = 22. р Е {132 , 152 , 154 , 168 , 196 , 198 , 224 , 252 , 264 , 266 , 294 , 308 , 342 , 392 , 396 , 418 , 456 , 462 , 504 , 528 , 588 , 616 , 684};

• (10)    t = 24. р Е {144 , 160 , 168 , 174 , 180 , 210 , 216 , 232 , 224 , 240 , 252 , 270 , 280 , 288 , 290 , 336 , 348 , 360 , 378 , 406 , 420 , 432 , 464 , 480 , 504 , 522 , 540 , 560 , 580 , 630 , 672 , 696 , 720 , 756 , 812 , 840};

• (11)    t = 29. р Е {180 , 203 , 210 , 225 , 252 , 261 , 290 , 300 , 315 , 348 , 350 , 406 , 420 , 435 , 450 , 522 , 525 , 580 , 609 , 630 , 700 , 725 , 812 , 870 , 1015};

• (12)    t = 30. р Е {210 , 216 , 252 , 270 , 280 , 360 , 362 , 420 , 504 , 540 , 630 , 724 , 840};

• (13)    t = 36. р Е {248 , 252 , 294 , 324 , 336 , 372 , 378 , 392 , 432 , 434 , 496 , 504 , 558 , 588 , 648 , 672 , 744 , 756 , 784 , 868 , 882 , 1008 , 1116 , 1134}.

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

• (1)    s = 10 и Г - граф Тэйлора:

• (2)    s = 7 ли 60 t = 1 и Г - докалыю T(9)-граф с массивом пересечений {36 , 21 , 10 , 3; 1 , 6 , 15 , 28} (половшшый 9-ксб( либо t = 18 и Г - граф с массивом перс- -™¹™ ^{512 . 378 , 1;1 , 189 . 512^}-

• (3)    s = 6 11 лпоо t = 4 и Г — граф с массивом пересечений {175 , 144 , 22; 1 , 24 , 154} пли {175 , 144 , 1;1 , 12 , 175}. mi 160 t = 8 л Г - граф с массивом пересечений {343 , 288 , 1; 1 , 96 , 343}.

Для доказательства, следствия полезен следующий результат.

Лемма 1 [4. теорема 20]. Пусть Г - дисташшошю регутарный граф диаметра d >  3 п степени k >  2. Есмп k₂ 6 3k/2 (равноеплвпо c ₂ >  2b 1 /3). то ввшодияется одно из следующих утверждений:

• (1)    d = 3 и Г - двудодвивш граф пли граф Тэйлора:

• (2)    Г - граф Джонсона J (7 , 3) пли 4-куб.

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

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

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

Лемма 3. Если диаметр Г больше 3. то . тибо s = 6 iit Е { 3 , 4 , 6 , 8 , 9 }. ж юо s = 7 и t = 1.

C Пусть Г содержит геоде:зический 4-путь u. w. x. y. z. Тогда в графе [ x ] между [ u ] П [ x ] ii [ x ] П [ z ] нет ребер ii ввиду леммы 2 имеем v(st — 5 t + s — 10) / ( st + s — 5) 6 w 6 ^{v(t + 6)/}(2 st + 2 s + ² t + ²⁾. Поэтому 2( s2 ⁺ s ⁺ t ⁺ l⁾( st ^— И ⁺ s ^— 1° 6 ( st ⁺ s ^— 5)( i + 6).

В случае s = 6 имеем 14(t+1)(t—4) 6 (6t+1)(t+6), поэтому t 6 9. Ввиду предложения t ^{Е{ 3}-⁴-^{6 8}-^9}-

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

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

Лемма 4. Если диаметр Г равен 3. то . тибо s = 10 п Г - граф Тэй лора, либо s = 9. t = 12 и 118 6 p 6 162. .тибо 6 6 s 6 8.

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

Пусть s = 9. Тогда k = v ' = ( s +1)(1+ st/ ( s —5)) = 5(9 t +4) / 2. А = k' = s ( t +1) = 9( t +1). b1 = 6 st/ ( s — 5) = 27 t/ 2 11 t делится на 4. Bbii, ту леммы 2 имеем (19 t + 14)2 p • x _o 6 (5(9 t + 4) / 2 — p )(5(9 t + 4) / 2 — x o)( t + 6)2.

Если t = 24. т о k = v ' = 550. А = k ' = 225. b1 = 324. 238 6 p 6 324 ii 4 • 238 • 2422 • x _o 6 4 • 2422 p • x _o 6 212(550 — x _o)30². поэтому x _o = 1. противоречие.

Значит, t = 12. k = v ' = 280. А = k ' = 117. b i = 162. 118 6 p 6 162 1i p де.тит 280 • 162.

Лемма 4, а вместе с ней и теорема 1 доказаны, в

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

C В случае параметров (133 , 24 , 5 , 4) по лемме 6 имеем 4 < р <  108. Так как р делит

• ²⁸ •²⁷ • 19. т.. р ^е (6 , 7 , 9 , 12 , 14 , 18 , 19 , 21 , 24 , 27, 28 , 36 , 38 , 42 , 54 , 57 , 63 , 76 , 84}.

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

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

Лемма 7. Справедливы следующие утверждения:

• (1)    ее.тп t = 4. то р е {6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 , 24 , 28 , 30 , 36 , 40 , 42 , 48 , 50 , 56 , 60 , 70 , 72 , 80 , 84 , 90 , 100 , 112 , 120 , 126 , 140 }. в елучае d (P) >  3 mi.хм р 6 25:

• (2)    ее.тп t = 6. то р е {18 , 24 , 28 , 36 , 42 , 54 , 56 , 72 , 74 , 50 , 84 , 108 , 126 , 148 , 168}. в случае d (r) >  3 ткmi р 6 31.

Лемма 8. Справедливы следующие утверждения:

• (1)    ее.тп t = 8. то р е {32 , 36 , 42 , 48 , 54 , 56 , 72 , 84 , 96 , 98 , 112 , 126 , 144 , 168 , 196 , 224 , 252 }. в случае б(Г) >  3 пм< чы р = 32 , 36:

• (2)    ее.тп t = 9. то р е {36 , 42 , 44 , 45 , 54 , 55 , 60 , 63 , 66 , 70 , 77 , 81 , 84 , 90 , 99 , 105 , 108 , 110 , 126 , 132 , 140 , 154 , 162 , 165 , 189 , 198 , 210 , 220 , 231 , 252 , 264 , 270 , 297 , 308 , 315}. в случае d (r) >  3 шкты р = 36.

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

• (1)    ее.тп t = 12. то р е { 72 , 84 , 108 , 112 , 126 , 144 , 146 , 168 , 216 , 252 , 292 , 336 , 378 }:

• (2)    ее.тп t = 14. то р е { 72 , 84 , 90 , 102 , 118 , 120 , 126 , 136 , 140 , 168 , 170 , 180 , 196 , 204 , 210 ,

238 , 252 , 280 , 294 , 306 , 360 , 392 , 408 , 420 , 476 , 490 }:

• (3)    ее. тн= = 15. то р е {78 , 84 , 90 , 91 , 98 , 105 , 108 , 117 , 126 , 130 , 140 , 135 , 147 , 156 , 180 , 182 , 189 , 195 , 196 , 210 , 234 , 245 , 252 , 260 , 270 , 273 , 294 , 315 , 351 , 364 , 378 , 420 , 441 , 455 , 490 , 510};

• (4)    ее. тп t = 22. то р е { 132 , 152 , 154 , 168 , 196 , 198 , 224 , 252 , 264 , 266 , 294 , 308 , 342 , 392 , 396 , 418 , 456 , 462 , 504 , 528 , 588 , 616 , 684}:

• (5)    ее. тп t = 24. то р е { 144 , 160 , 168 , 174 , 180 , 210 , 216 , 232 , 224 , 240 , 252 , 270 , 280 , 288 , 290 , 336 , 348 , 360 , 378 , 406 , 420 , 432 , 464 , 480 , 504 , 522 , 540 , 560 , 580 , 630 , 672 , 696 , 720 , 756 , 812 , 840 ^}:

• (6)    ее. тп t = 29. то р е { 180 , 203 , 210 , 225 , 252 , 261 , 290 , 300 , 315 , 348 , 350 , 406 , 420 , 435 , 450 , 522 , 525 , 580 , 609 , 630 , 700 , 725 , 812 , 870 , 1015}:

• (7)    ее.тп t = 30. то р е { 210 , 216 , 252 , 270 , 280 , 360 , 362 , 420 , 504 , 540 , 630 , 724 , 840 }:

• (8)    ее. тп t = 36. то р е { 248 , 252 , 294 , 324 , 336 , 372 , 378 , 392 , 432 , 434 , 496 , 504 , 558 , 588 , 648 , 672 , 744 , 756 , 784 , 868 , 882 , 1008 , 1116 , 1134}.

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

В случае параметров (511 , 78 , 5 , 13) имеем 56 < р <  432. Так как р дед нт 84 • 36 • 73. то р ^е { 72 , 84 , 108 , 112 , 126 , 144 , 146 , 168 , 216 , 252 , 292 , 336 , 378^}.

В случае параметров (595, 90, 5,15) имеем 70 < р < 504. Так как р делит 98 • 36 • 85, то р е {72 , 84 , 90 , 102 , 118 , 120 , 126 , 136 , 140 , 168 , 170 , 180 , 196 , 204 , 210 , 238 , 252 , 280 , 294 , 306 , 360 , 392 , 408 , 420 , 476 , 490^}.

В случае параметров (637, 96, 5,16) имеем 77 < р < 540. Так как р делит 42 • 90 • 91. то р е {78 , 84 , 90 , 91 , 98 , 105 , 108 , 117 , 126 , 130 , 140 , 135 , 147 , 156 , 180 , 182 , 189 , 195 , 196 , 210 , 234 , 245 , 252 , 260 , 270 , 273 , 294 , 315 , 351 , 364 , 378 , 420 , 441 , 455 , 490 , 510}.

В случае параметров (931 , 138 , 5 , 23) имеем 126 < р <  792. Так как р дед нт 931 • 792. то р е {132 , 152 , 154 , 168 , 196 , 198 , 224 , 252 , 264 , 266 , 294 , 308 , 342 , 392 , 396 , 418 , 456 , 462 , 504 , 528 , 588 , 616 , 684}.

В случае параметров (1015,150, 5, 25) имеем 140 < ц <  864. Так как ц дел нт 1015 • 864. то ц € {144,160,168,174,180, 210, 216, 232, 224, 240, 252, 270, 280, 288, 290, 336, 348, 360, 378,406,420,432,464,480, 504, 522, 540, 560, 580, 630, 672, 696, 720, 756,812, 840}.

В случае параметров (1225,180,5,30) имеем 175 < ц < 1044. Так как ц делит 1225 • 1044. то ц € {180,203,210, 225, 252, 261, 290, 300, 315, 348, 350,406, 420,435,450, 522, 525,580,609,630,700, 725,812,870,1015).

В случае параметров (1267,186,5, 31) имеем 182 < ц < 1080. Так как ц дел нт 1267 • 1080. то ц € {210, 216, 252, 270, 280, 360, 362,420, 504, 540,630,724,840}.

В случае параметров (1519,252,5,37) имеем 224 < ц < 1296. Так как ц делит 1519 • 1296. то ц € {248,252,294, 324, 336, 372, 378, 392, 432,434,496, 504, 558,588, 648, 672, 744, '56, 784,868,882,1008,1116,1134}.

B

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

В этом параграфе предполагается, что Г - дистанционно регулярный граф диаметра d > 3, в котором окрестности вершин — псевдогеометрические исключительные графы для pG_s-5(s, t). Пусть 90 >91 > ••• > 9d - собственные :значения графа Г. Зафиксируем вершину u € Г ii положим ki = |ri(u)|. Ес -ди s = 6. то по [8. теорема 4.4.3] верив! неравенства, -(t + 1) >  b^- = -1 - b1/(91 + 1) ii 5 6 b+ = -1 - b1/(9d + 1). Так как b1 = 36, то 9d > -6t - 1 и 91 6 35. Ввиду границы Тервиллигера [6, следствие 5.2.2] имеем d 6 (k + cd)/(a1 + 2). позтому d 6 14(6t + 1)/(6t + 8).

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

• (1)    s = 6. t = 4 н Г - граф с массив ом пересечений {175,144,40,1; 1,10,144,175}:

• (2)    s = 7. t = 1 пГ - половинный 9-куб.

C Пусть дпамстр Г больше 3 11 u. w. x. y. z- геодезическин путь в Г. В елучае s = 7 по лемме 3 имеем t = 1 ii 32ц 6 36 • 7. позтому ц = 6 11 ц-подгр;1фы в Г - октаэдры. Палее, для вершины u € Г граф А = [u] — треугольный граф T (9). В этом случае Г -половинный 9-куб.

Если s = 6. то по лсмэж 2 имеем t € {3,4,6, 8, 9} 11ц 6 (t + 6)(6t + 1)/(2t + 2). Далее. 7(t - 4) 6 див случае t = 9 имеем 35 6 ц 6 41. Так как ц дел нт 7(6t + 1)36t. то в этом случае ц = 36. k2 = 63 • 55. По лемме 2 имеем 125236b2 6 (385 - 36)(385 - b2)152. поэтому b2 6 47. С другой стороны. с3 > 3ц/2 = 54. позтому d = 4. С помощью компьютерных вычислений получим, что в этом случае допустимых массивов пересечений нет.

По [6, лемма. 3.2.1] средняя степень графа, не превосходит его наибольшего собственного значения, причем равенство достигается только в случае регулярного графа. Поэтому мы ищем шар наименьшего радиуса г, в котором средняя степень не меньше -b1/(n2 + 1) - 1, г Де П1 ->72 неглавные собственные значения окрестности вершины. Согласно [6, теорема 4.4.3] в графе Г не может быть двух изолированных шаров радиуса г. значит, d 6 2г + 1.

По условию окрестности вершин в Г сильно регулярны с параметрами (42t + 7,6t + 6, 5, t + 1). Тогда b1 = 36t. n1 = 5,n2 = -(t + 1). Ес -ли d > 4. то k = k - b₂k₂/v₂< -b1/(n2 + 1)-1 = 35, противоречие. Значит, d 6 4. С помощью компьютерных вычислений получим, что t = 4 ii Г имеет массив пересечений {175,144,40,1; 1,10,144,175}. B

Замечание. Графа с массивом пересечений {175,144,40,1;1,10,144,175} не существует.

C Граф с массив! dm пересечений {175,144,40,1;1,10,144,175} являсмея AT4(5, 5, 5)-графом ii согласно [7] не существует. B

Лемма 11. Если d = 3 и s >  7 , то s = 7 , t = 18 и Г — граф с массивом пересечений {512 , 378 , 1; 1 , 189 , 512}.

C Пусть диамстр Г равен 3.

Если s = 9. то по лсмэю 4 имеем t = 12. k = 280. b1 = 162 ii 118 6 p 6 162. Ввиду леммы 1 получим p 6 108. противоречие.

Если s = 8. то t = 2,4, 6, 9,10,12,14,18, 24, 30,34, 39,42, 54, 66, 74, 84 и ввиду леммы 2 имеем k(3t - 2)/(8t + 3) 6 p 6 4k/9. г.ле k = 3(8t + 3). Так как b1 = 22t + 1. то по лемме 1 имеем p < (44t + 2)/3. С помощью компьютерных вычислений получим, что в этом случае допустимых массивов пересечений нет.

Если s = 7. то t = 1,4, 6, 8, 9,14,15,18, 22, 24, 29, 34, 36, 50, 54 и ввиду леммы 2 имеем k(2t - 3)/(7t + 2) 6 p 6 3k/8. г.ле k = 4(7t + 2). Так как b1 = 27t + 1. то по лемме 1 имеем p < (54t + 2)/3. С помощью компьютерных вычислений получим, что в этом случае t = 18 ii Г - граф с массив ом пересечений {512, 378,1; 1,189, 512}. B

Лемма 12. Если d = 3 iis = 6. то . либо t = 4 н Г - граф с массивом пересечений { 175 , 144 , 22; 1 , 24 , 154 } или { 175 , 144 , 1; 1 , 12 , 175 }. miюо t = 8 и Г — граф с массивом пересечений { 343 , 288 , 1; 1 , 96 , 343 }.

• C Пусть диамстр Г равен 3 iis = 6.

Если t = 3. то ввиду леммы 1 и теоремы 2 имеем 6 6 p 6 63. В любом случае допустимых массивов пересечений нет.

Если t = 4. то ввиду леммы 1 и теоремы 2 имеем 6 6 p 6 90. С помощью компьютерных вычислений получим, что Г - граф с массивом пересечений {175 , 144 , 22; 1 , 24 , 154} ■™{175 , 144 , 1:1 , 12 , 175^}.

Если t = 6. то ввиду леммы 1 ii теоремы 2 имеем 18 6 p 6 126. В люиом случае допустимых массивов пересечений нет.

Если t = 8. то ввиду леммы 1 и теоремы 2 имеем 32 6 p 6 168. С помощью компьютерных вычислений получим, что Г - граф с массивом пересечений {343 , 288 , 1;1 , 96 , 343 }.

В случае t > 8 допустимых массивов пересечений нет. Лемма 12 и следствие из § 1 доказаны. B