Содержание к диссертации
Введение
Глава 1. Однородные расширения частичных геометрий и обобщенных четырехугольников
1. Расширения частичных геометрий
2. Вполне регулярные локально С 5(4,)-графы
Глава 2. Графы с малыми значениями Ь\ и локально циклические дистанционно регулярные графы
3. Графы с Ь\ = 6
4. Сильно регулярные графы с Ь\ 24
5. Автоморфизмы дистанционно регулярных графов с не более 1000 вершинами
6. Дистанционно регулярные графы с ц = 1 и не более 1000 вершинами
Глава 3. Плотные сферические схемы, 4-изорегулярные графы и их автоморфизмы
7. Сильно регулярные подграфы из Izo(r)
8. Автоморфизмы сильно регулярных подграфов из Izo(r)
Глава 4. Вполне регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2, и небольшие сильно регулярные графы
9. Графы, в которых окрестности вершин сильно регулярны с собственным значением 2
10. Автоморфизмы небольших сильно регулярных графов
Глава 5. Дистанционно регулярные графы с Л = 2 и не более 4096 вершинами
11. Графы с ц = 1
12. Графы с ц 1
Литература
- Вполне регулярные локально С 5(4,)-графы
- Автоморфизмы дистанционно регулярных графов с не более 1000 вершинами
- Автоморфизмы сильно регулярных подграфов из Izo(r)
- Автоморфизмы небольших сильно регулярных графов
Вполне регулярные локально С 5(4,)-графы
Доказательство. Если s = 71, то = 23r, г 80о;/71 и а делит t. Поэтому г = г о! и 1633г + 4 делит 72 73 4, противоречие.
Если s = 72, то t = 35г, г 20о;/27 и 72г = г а. По лемме 1.6 число 35г + 4 делит 12 73 37, противоречие.
Если s = 73, то t = 71г, г 26 и а делит г. Поэтому г = г а и 71г + 4 делит 74-75-12, противоречие.
Если s = 74, то Д = 37/(Зо;), t = Зг, г 640 и а делит 37г. Допустим, что а = 37. Тогда г 12 и Зг + 2 делит 2 25 19. Если 19 делит Зг + 2, то г = 12 + 19м и Зм + 2 делит 50. Поэтому и Є {0,1,16}. В случае и = 0 получим Д = 12, а если и 0, то нарушается условие целочисленности для рСз7(74, 36 + 57м). Значит Зг + 2 делит 50, г = 16 и нарушается условие целочисленности для pG37(74, 48).
Итак, t = Зг а и по лемме 1.6 число 111г + 2 делит 25-4, противоречие. Лемма доказана.
До конца параграфа предполагается, что S — сильно (s—2)-однородная геометрия EpGa(s,t), 10 s 70. Ввиду лемм 1.6-1.9 можно предположить, что Д {12,16} и t ф а. Лемма 1.11. Верно неравенство s 60. Доказательство. Пусть s = 61. Тогда t = 59r, г 80о;/183 и а делит г. Противоречие с тем, что г = г1 а иг 80/183.
Пусть s = 62. Тогда Д = 62/(5о;), t = Ъг и г 160о;/31. Если а = 31, то по лемме 1.6 число 5г + 32 делит 63-64- 31 и 5г + 2 делит 32-21-6. Если 31 делит Ъг + 32, то г = 6 + 31м, 5г + 2 = 155м + 32 делит 32 21 6, и = 0 и Д = 12, противоречие. Значит, а делит 2г. Заметим, что наибольший общий делитель чисел 5г + 32 и 5г + 2 делит 30, и если 5г + 2 делится на 7, то г = 8 и по условию целочисленности для pGa(62, 40) число а(103 — а) делит 62-63-40-41, противоречие. Если 5г+32 делится на 7, то г = 2 + 7м и 5г + 2 = 35м+12 делит 64-9, поэтому и = 0 и по условию целочисленности для pGa(62,10) число а(73 — а) делит 62 63 10 11, противоречие. Итак, Ъг + 32 делит 9 64 и 5г + 2 делит 64 3, противоречие.
Пусть s = 63. Тогда t = 6lr, г 80о;/189 и а делит г. Противоречие с тем, что г = г а иг 80/189.
Пусть s = 64. Тогда Д = 12st/(a(s — 2)) = 6 64/(31а;), поэтому t = 31г и г 5а/6. Далее, а делит 64г, 64г = г а и г 160/3. По лемме 1.6 число 31г + 4 делит 65 33 12. Если 13 делит 31г + 4, то г = 7 + 13м Є {20,46}. Но в случае г = 20 имеем 31г + 4 = 13 48, поэтому г = 46, г = 23, а = 32 и нарушается условие целочисленности для рСз2(64, 31 23). Если 11 делит 31г + 4, то г = 2 + 11м Є {2, 24,46}. Но в случае г = 24 имеем 31г + 4 = 187 4, поэтому г = 2, 32г = а и Д = 12, противоречие. Значит, 31г + 4 делит 15 12, противоречие.
Пусть s = 65. Тогда Д = 12st/(a(s — 2)) = 260t/(21a), t = 21г и г 80о;/65. Далее, а делит 65г, поэтому 65г = г а, г 80, г не взаимно просто с 65 и по лемме 1.6 число 21г + 4 делит 4 22 67. Если 67 делит 21г + 4, то с учетом равенства (67, 21г + 4) = (67, г — 3) получим г = 70. Поэтому 13г = 14о! и (г, а) Є {(13,14), (28, 26), (42, 39), (56, 52)}. В любом случае нарушается условие целочисленности для pGa(s,t).
Значит, 21г + 4 делит 12-22 и 11 делит г —4. Поэтому г Є {15, 26, 70}. В любом случае 21г + 4 12-22, противоречие.
Пусть s = 66. Тогда Д = 12st/(a(s — 2)) = 99/(8а;), поэтому t = 8г и г 5 64о;/99. Далее, а делит (66, 99г), поэтому ЗЗг = г а иг 1280/3, г не взаимно просто с 33 и по лемме 1.6 число 1 + 2г делит 67-51. Если 67 делит 1 + 2г , то г = 33, а = 2г и г 31. По условию целочисленности для pG2r(66, 8г) число 67 + 6г делит 33 67(8г + 1). Так как (67 + 6г, 33) = (11, 6г + 1) и (67 + 6г, 8г + 1) = (67 + 6г, г — 33) делит 265 = 5 53, то г = 33, противоречие.
Итак, 2г + 1 делит 51 и г = 8. Поэтому а = 33, г = 4 и Д = 12, противоречие. Пусть s = 67. Тогда Д = 12st/(a(s — 2)) = 12 67t/(65o;), поэтому t = 65r, г = г а и г 80 65/201. По лемме 1.6 число 67 65г + 4 делит 12 68 69, противоречие. Пусть s = 68. Тогда Д = 12st/(a(s — 2)) = 136i/(llo;), поэтому t = llr и г 40о;/17. Далее, а делит 68г, 68г = г а и г 160. По лемме 1.6 число llr + 4 делит 12 23 35. Если 23 делит llr + 4, то г = 8 + 23м Є {8,54,100,146}. В случае г = 8 имеем 17г = 2а. Если а = 17, то г = 2 и нарушается условие целочисленности для pG17(68, 22). Если а = 34, то г = 4 и нарушается условие целочисленности для рСз4(68,44). Если а = 51, то г = 6 и нарушается условие целочисленности для рСбі(68, 66). В случае г = 54 имеем г = 27, а = 34 и нарушается условие целочисленности для рСз4(68, 297). В случае г = 100 имеем 17г = 25 х Если а = 17, то г = 25 и нарушается условие целочисленности для pG17(68, 275). Если а = 34, то г = 50 и нарушается условие целочисленности для рСз4(68, 550). Если а = 51, тог = 75и нарушается условие целочисленности для рСбі(68, 825). В случае г = 146 имеем г = 73, а = 34 и нарушается условие целочисленности для рСз4(68, 803).
Значит, 11г + 4 делит 12 35. Если 7 делит 11г + 4, то г = 6, противоречие с тем, что тогда Д = 12. Значит, 11 г + 4 делит 60, противоречие.
Пусть s = 69. Тогда t = 67г, 69г = г а иг 80/3. По лемме 1.6 число 67г + 4 делит 12 70 71. Если 71 делит 67г + 4, то г = 1, противоречие. Значит, 67г + 4 делит 12 70, снова противоречие.
Пусть s = 70. Тогда Д = 12st/(a(s — 2)) = 210t/(17a), поэтому t = 17 г и г 32а/21. Далее, а делит 70г, 70г = г а и г 320/3. По лемме 1.6 число 17г + 4 делит 12-71-18. Если 71 делит 17г + 4, то г = 100, 7г = 10а и нарушается условие целочисленности для pGju{70,170м), и 9. Значит, 17г + 4 делит 12-18иг = 4. Поэтому г = 2, а = 35, противоречие с тем, что Д = 12. Лемма 1.12. Параметр s не больше 50. Доказательство. Пусть s = 51. Тогда t = 49г, г 80о;/153 и а делит 51г. Положим 51г = г а. Тогда st/a = 49r , г 80/3 и по лемме 1.6 число 49г + 4 делит 12 52 53. Если 53 делит 49г + 4, то г = 1, противоречие. Значит, 49г + 4 делит 12 52, г = 4м и 49м + 1 делит 156, противоречие.
Пусть s = 52. Тогда Д = 12st/(a(s — 2)) = 312t/(25a), поэтому t = 25r и г 40о;/39. Далее, а делит 52г, поэтому 52г = г а, г 160/3 и по лемме 1.6 число 25г + 4 делит 12 53 27. Если 53 делит 25г + 4, то 53 делит г + 15 и г = 38. В этом случае г = 19,а = 26 и нарушается условие целочисленности длярС2б(52, 25-19). Значит, 25г +4 делит 12-27, поэтому 27 делит г — 2, г = 2, г = 1,а = 26, противоречие с тем, что тогда Д = 12.
Пусть s = 53. Тогда t = 17г, г 80о;/53 и а делит г. Так как г = г а и г 80/53, то г = аи нарушается условие целочисленности для рСбі(54, 53 17).
Пусть s = 54. Тогда Д = 12st/(a(s — 2)) = 162t/(13a), поэтому t = 13r и г ІбОа/81. Далее, а делит 54г, поэтому 54г = г а, г 320/3 и по лемме 1.6 число 13г + 4 делит 12-55-56. Если 11 делит 13г + 4, то г = 20, г = 10, а = 27 и нарушается условие целочисленности для pG27(54,130).
Автоморфизмы дистанционно регулярных графов с не более 1000 вершинами
Допустим, что Сз(и,у) = 9 для некоторой вершины у Є Гз(м), и положим [и] П Г3(у) = {w}, [у] П Г3(м) = {г}. Пусть Г3(м) П Г3(у) содержит вершину z, [и] — Г2(г) = {w\, ...,Wi}, где / = 10 — Сз(м,г), и А = Г2(и) — ([у] U [z]). Тогда [w] содержит 3 вершины из А, в частности, Cs(u,z) 8. Если Cs(u,z) = 8, то А = 3 и А С [WJ\ для і Є {1,2}. Противоречие с тем, что [w\] П [и)2\ содержит и и 3 вершины из А.
Значит, Сз(м, z) = 7 и А = 4. Далее, каждая вершина из {w, Wi,..., w } смежна с 3 вершинами из А. Поэтому для 2-путей с концами в А не более 6 средних вершин попадают в Г3(м). Если для вершины s из Г3(м) — {у, z} подграф [s] П Г2(м) содержит точно 1 вершину из А, то Сз(и, s) = 7. Противоречие с леммой 6.13. Значит, для любой вершины s из Гз(м) — {у, z} подграф [s] П Г2 (и) содержит 2 вершины из А и по 3 вершины из [у], [z]. Противоречие с тем, что для q Є Г3(м) П [z] и s Є Г3(м) П [q] — {z} подграф [s] П Г2(м) содержит не более 2 вершин из [z].
Итак, Гз(м) — {у} содержится в Г2(у). Если Сз(и,г) = 9, то каждая вершина из Гз(м) — {у} смежна с 3 вершинами из (и) П [у], поэтому каждая вершина из Г2(и)П[у] смежна точно с 2 вершинами из Гз(м) — {у}. Ввиду леммы 3.7 каждая вершина из Г2(м) П [у] — [г] смежна с ребром из Г3(м) — {у,г}. По лемме 3.13 имеем Cs(u,z) 8 для любой вершины z Є Гз(м). Если Cs(u,z) = 9 для некоторой вершины z Є Гз(м) — {у, г}, то Yg = 4, \Ys\ = 3 и каждая вершина из А смежна с 3 вершинами из Гз(м) — {у, г}. Противоречие с тем, что Гз(м) — {у, г} содержит точно 4 ребра, каждое из которых попадает в окрестности 3 вершин из Г2(м) П (([у] — [z]) U ([z] — [у])). Значит, Г3(м) — {у, г} является пятиугольником, и А содержит 2 вершины, смежные с 2-кокликами из Гз(м) — {у, г}, и 3 вершины, смежные с изолированной вершиной и ребром из Гз(м) — {у, г}. Теперь число 2-путей с концами в Гз(м) — {у, г} и средней вершиной в А равно 10, противоречие.
Таким образом, Сз(м,г) 8. Пусть Сз(м,г) = 7, [г] П (Г3(м) — {у}) = {р!,р2}. Ввиду леммы 3.13 каждая вершина из Г3(м) — г± смежна с вершиной из {рі,р2}. Без ограничения общности, р\ смежна с 2 вершинами из Г3(м) — г± и Cs(u,p\) = 7. Отсюда Г2(и) П [г] П [р\]\ = 3, противоречие с леммой 3.12.
Значит, Сз(и,г) = 8 и [г] П (Гз(м) — {у}) содержит единственную вершину р. Тогда р смежна точно с 2 вершинами из Г2(и) П [у], а любая вершина из Г3(м) — {у,р} смежна с 3 вершинами из Г2(и) П [у], поэтому точно одна вершина х из Г2(и) П [у] смежна с единственной вершиной из Гз(м) — {у}, а любая вершина из Г2(и) П [у] — {х} смежна точно с 2 вершинами из Гз(м) — {у}. Далее, Сз(и, q) 8 для q Є Гз(м) — {р}.
Если Гз(м) — {у,г,р} С Г2(г), то Сз(и,р) = 7, число ребер между Г2(м) П [г] и Г3(м) — {г} равно 16 и каждая вершина из Г2(м) П [г] смежна с 2 вершинами из Г3(м) — {г}.
Пусть Сз(и,р) = 7. Тогда число ребер между Г2(м) П [р] и Гз(м) — {р} не больше 14, но не меньше 2 + 3 + 10, противоречие.
Значит, Сз(и,р) 7 и Гз(и) —{у, г,р} содержит вершину z из Гз(г). Тогда Г2 (и) П [z] содержит 3 вершины из [у] и 5 из 6 вершин в Г2 (и) — ([у] U [г]). Если вершина из Г2(м) П [у] П [г] смежна с р, то либо Сз(и,р) = 9 и А содержит не менее 4 вершин из [р] П [z], либо Сз(и,р) = 8, [р] П [z] содержит 3 вершины из А и вершину из Гз(м). В любом случае имеем противоречие. Итак, вершины из Г2(м) П [у] П [г] несмежны с р, поэтому Г2(м) П [р] содержит 2 вершины из [у] — [г]. Теперь Г2(м) П [р] содержит вершину, смежную с 2 вершинами из Г3(м), и вершину, смежную с вершиной s из Г3(м) П [р]. Положим Ф = [у] П Г2(м) — ([р] U [г]). Тогда [у] П [s] содержит по вершине из [р], [г] и из Ф. Поэтому Г2(м) П [s] содержит 4 вершины из Г2(м) — ([у] U [г]), 3 из которых попадают в [z]. Отсюда Ф — [s] = [у] П [z] и Сз(и, s) = Сз(и, z) = 8, в частности, вершины s, z смежны. Теперь каждая из вершин s , s", принадлежащих Г3(м) — ({s,z} U г-1), смежна с 2 вершинами из Ф П [z], противоречие.
Таким образом, Гз(м) не содержит вершин у с Сз(и,у) = 9. Допустим, что для любой вершины у Є Гз(м) имеем Сз(и,у) = 8. Тогда Гз(м) является семиугольником или объединением треугольника и четырехугольника, а число ребер между Г2(м) и Г3(м) равно 56. Так как вершины из Г2(м), смежные с парами противоположных вершин четырехугольника, несмежны с вершинами треугольника, то Г2(м) содержит 6 вершин, смежных с парами вершин треугольника, и 12 вершин, каждая из которых смежна с одной вершиной треугольника. По лемме 2.1 любая из этих 12 вершин смежна с ребром четырехугольника. Поэтому из 6 вершин, смежных с парами вершин треугольника, точно 2 несмежны с вершинами четырехугольника. Значит, найдется вершина z треугольника, смежная с единственной вершиной х, имеющей Ь2(м,ж) = 2. Противоречие с тем, что число 2-путей с началом z и концом в четырехугольнике равно 13. Пусть Г3(м) является семиугольником. Если d(y,z) = 3 для некоторых вершин y,z Є Гз(м), то число ребер между (и) — ([у] U [z]) и Гз(м) — {у, z} равно 4 + 2-3 + 2-2 = 14. Теперь некоторая вершина из ГгС ) — ([у] U [z]) смежна с 4 вершинами из Гз(м) — {у, z}, противоречие. Значит, d(y, z) 2 для любых вершин у, z Є Г3(м). Поэтому число ребер между Г2(м) П [z] и Г3(м) — {z} равно 4-3 + 2-2 = 16 и каждая вершина из (и), смежная с вершиной из Гз(м), смежна с 3 вершинами из Гз(м). Противоречие с тем, что число ребер между Г2(и) и Гз(м) не кратно 3.
Таким образом, Гз(м) содержит 2 вершины y,z из IV. Через а обозначим Г2(м) П [у] П [z]. Если а = 0, то d(y,z) 2, иначе Г3(м) 8. В этом случае [у] П [z] содержит 3-коклику {гі,Г2,Гз}, Г3(м) — (у-1 U z-1) содержит ребро {s\,S2}, и можно считать, что вершина s\ смежна с г\, S2 смежна с Гг. Поэтому ( (и) П [у] П [г\]\ = 3, противоречие с леммой 3.12. По лемме 3.12 получим а ф 3.
Если а = 1, то по лемме 3.16 имеем \[и] П Г2(у) П Г2(г) = 4. Далее, Г3(м) содержит 2 вершины Гі,Г2 из [у] П [z]. Если вершины у, z смежны, то Г3(м) — (у-1 U Z"1) содержит вершину s, не смежную ни с Г\, ни с Гг. Поэтому [у] П [s] П Г2(м) = 3, противоречие с леммой 3.12. Значит, вершины y,z не смежны, и Гз(м) содержит вершину у , смежную с у, вершину z , смежную с z и еще одну вершину s. Если вершина г І смежна с s, то Г2(м) П [у] П [гі\\ = 3, противоречие с леммой 3.12. Значит, Г3(м) П [s] = {y ,z }. Если вершина у не смежна с вершинами из {г+Гг, z }, то Г2(м) П [у ] П [z] = 3, противоречие с леммой 3.12. Если вершина у не смежна с вершинами из {г+Гг}, то Г2(м) П [у ] П [у] = 3, снова противоречие с леммой 3.12. Итак, можно считать, что у смежна с г\, z1 смежна с г2. Но в этом случае Г2(м) П [у] П [гг] = 3, противоречие с леммой 3.12.
Значит, а = 2, по лемме 3.11 число \[и] ПГ2(у) ПГ2(г) равно 5. Далее, Гз(м) содержит единственную вершину г из [у] П [z].
Если вершины y,z смежны, то Гз(м) содерж;ит вершину у , смежную с у, вершину z , смежную с z и вершины S\, S2, несмежные ни с у ни с z. Так как одна из вершин S\, S2 не смежна с г, то можно считать, что S\ не смежна с г и ввиду леммы 3.12 вершина s\ смежна с y ,z . Поэтому S\ Є Is. Далее, [S2] содержит 2 вершины из {г, y ,z }, попадающие в Yj, и имеющие двух общих соседей в Гз(м), противоречие.
Итак, Yj — коклика, и вершины у, z не смежны. Тогда Г3(м) содержит 2 вершины yi, у2 из [у] - [г] и 2 вершины Zi, Z2 из [z] — [у]. Если У7 = 2, то либо {у1; у2} и {zi, Z2} — ребра, либо {у1; Zi} и {у2, Z2} — ребра. В любом случае число ребер между Г2(и)П[у] и Гз(м) — {у} равно 15, противоречие. Поэтому \Yj\ 4. Противоречие с тем, что Y? — коклика. Лемма, а вместе с ней и теорема 3.1 доказаны.
Автоморфизмы сильно регулярных подграфов из Izo(r)
В этой главе выяснены связи между плотными сферическими 4-схемами и 4-изорегулярными графами Izo(r). Найдены параметры сильно регулярных локальных подграфов из Izo(r) и возможные автоморфизмы Izo(r) с простейшими подграфами неподвижных точек. Завершено описание автоморфизмов сильно регулярных локальных подграфов из Izo(3).
Для подмножества вершин S графа Г через T(S) обозначим naes([a] S).
Граф Г называется t-однородным, если для любого г t и для любых двух изоморфных г-вершинных подграфов Ф и Ф найдется такой автоморфизм д графа Г, что Фд = Ф. Граф Г на v вершинах называется абсолютно однородным, если он является (v — 1)-однородным. Гарди-нер [57] доказал, что каждый 5-однородный граф Г является абсолютно однородным, и с точностью до перехода к дополнительному графу, Г является полным многодольным графом Ктхп, пятиугольником, или 3 х 3-решеткой.
Граф Г называется t-изорегулярным, если для любого г t и любого г-вершинного подмножества S число (S)! зависит только от изоморфного типа подграфа, индуцированного S. Как и выше, определяется абсолютно изорегулярный граф, t-изорегулярный граф Г называется точно t-изорегулярным, если он не является {t + 1)-изорегулярным. Камерон [26, теорема 8.21] доказал, что каждый 5-изорегулярный граф Г является абсолютно изорегулярным и принадлежит списку графов в за ключении теоремы Гардинера, а каждый точно 4-изорегулярный граф, с точностью до перехода к дополнительному графу, является псевдогеометрическим графом для pGr(2r, 2г3 + Зг2 — 1). Через Izo(r) обозначим псевдогеометрический граф для pGr(2r, 2r3 + 3г2 — 1). При г = 1 получим точечный граф единственного обобщенного четырехугольника порядка (2,4), а при г = 2 — граф Маклафлина. А.А. Махнев [28] доказал, что граф Izo(r) не существует в случае г = 3. Им же была выдвинута
Гипотеза. Ддя г 2 граф Izo(r) не существует.
Существование плотной сферической 5-схемы в Sn l (см. [27]) равносильно существованию графа Izo(r), где п = (2г + 1)2 —2. В [27, следствие 4.7] доказано несуществование плотных 5-схем для бесконечного набора значений параметра г: 3,4, 6,10,12, 22, 28, 30, 34, 42, 46,... .
Пусть Г = Izo(r), а — вершина графа Г, Е = [а], А = Г2(а), b Є [а], с Є Г2(а). Из условия 4-изорегулярности следует, что подграфы Е, А, Е(Ь), Е2(6), А(с), А2(с) сильно регулярны. В предложениях 3.1-3.3 найдены параметры этих графов. Предложение 3.1. Пусть Г — псевдогеометрический граф дляpGr(2r, 2г3 + Зг2 — 1). Тогда он имеет v = 8г4 + 16г3 + 6г2 — 2г — 1 вершин и собственные значения к = 4г4 + 6г3,г, —(2г3 + Зг2) кратностей 1,/ = 8г4 + 16г3 + 2г2 — 6r, g = 4г2 + 4г — 2 соответственно. Далее, для любой вершины а (1) подграф Е = [а] — псевдогеометрический граф для pGr-\(2r — 1, г3 + г2 — г — 1), имеет i i = 4г4 + 6г3 вершин и собственные значения к\ = 2г4 + г3 — Зг2 + г, Гі = r,S\ = —(г3 -\- г2 — г) кратностей l,f\ = 4r4 + 6r3 — 4r2 — 4r + 2, 7i = 4r2 + 4r — 3 соответственно; (2) подграф A = Гг(а) сильно регулярен, имеет г 2 = 4г4 + Юг3 + 6г2 — 2г — 2 вершин и собственные значения &2 = 2г4 + Зг3, Гг = г, S2 = — (г3 + 2г2) кратностей 1, /2 = 4г4 + Юг3 + 2г2 — 6r, д = 4г2 + 4г — 3 соответственно. Предложение 3.2. Пусть Е является псевдогеометрическим графом для pGr-\(2r — 1, г3 + г2 — г — 1). Тогда он имеет v = 4г4 + 6г3 вершин и собственные значения к = 2г4 + г3 — Зг2 + г,г, —(г3 + г2 — г) кратностей 1, / = 4г4 + 6г3 — 4г2 — 4г + 2, g = 4г2 + 4г — 3 соответственно. Далее, для любой вершины b Є Е (1) подграф Е(Ь) — псевдогеометрический граф для pGr_2(2r — 2, (г3 — Зг — 2)/2), имеет v\ = 2г4 + г3 — Зг2 + г вершин и собственные значения г4 — г3 — Зг2 + Зг, г, —(г3 — Зг)/2 кратностей 1, fi = 2r4 + г3 — 7r2 — Зг + 3, gi = 4r2 + 4r — 4 соответственно; (2) подграф T.2(b) сильно регулярен с параметрами (2r4+5r3+3r2 — г — 1,г4 + г3 — г2, (г4 — г3 — Зг2 + Зг)/2, (г4 —r2)/2) и собственными значениями г4__гз_г2 г — (г3 + 2г2 — г)/2 кратностей 1, 2r4+5r3 —г2 —5r+2, 4г2+4г —4 соответственно. Предложение 3.3. Пусть А является сильно регулярным графом с параметрами (4г4 + Юг3 + 6г2 — 2г — 2, 2г4 + Зг3, г4 — 2г2 + г,г4 + г3) и собственными значениями к = 2г4 + Зг3,г, —(г3 + 2г2) кратностей 1, 4г4 + Юг3 + 2г2 — 6г, 4г2 + 4г — 3 соответственно. Если г 2, то для любой вершины с Є А (1) подграф А (с) является сильно регулярным графом с параметрами (2г4 + Зг3, г4 — 2г2 + г, (г4 — 2г3 — Зг2 + 6г)/2, (г4 — г3 — 2r2 + 2r)/2) и собственными значениями г4 — 2г2 + г, г, —(г3 + г2 — 2г)/2 кратностей 1, 2г4 + Зг3 — 4г2 — 4г + 3, 4г2 + 4г — 4 соответственно; (2) подграф А2(с) сильно регулярен с параметрами (2г4 + 7г3 + 6г2 — 2г — 3, г4 + 2г3, (г4 — Зг2 + 2г)/2, (г4 + г3)/2), собственными значениями г4 + 2г3, г, —(г3 + Зг2)/2 кратностей 1, 2г4 + 7г3 + 2г2 — 6г, 4г2 + 4г — 4 соответственно. Далее, с помощью метода Хигмена для автоморфизма g графа Izo(r) найдена формула для значения характера, полученного при проектировании на подпространство размерности 4г2 + 4г — 2 Хїія) = (ao(g) — ai(g) /Т) / (if + 1)(2г + 1)) + (2г + 2г — 1)/(г + 1).
Найдены возможные простые порядки автоморфизмов g графа Izo(r) таких, что подграф Q = Fix(g) является пустым, кликой или кокликой. Теорема 3.1. (1) Если Q — пустой граф, то (і) р делит (2г + 1)(4г3 + 6г2 — 1), в частности, р ф 2, (и) еслир = 3, то г = 1 (mod 3), a\(g) = wr(2r-\-l) иw-\-l делится на г + 1. (2) Если О, является п-кликой, то п = 1 и либо р = 37, г = 37м + 17, либо р = 2. (3) Если Q является т-кокликой, т 2, то 3 т 4г2 + 4г — 2, р делит г и т + 1. Сначала приведем вспомогательные результаты. Лемма 7.1. Пусть Г является сильно регулярным графом с параметрами (г , к, Л, /Л) и неглавными собственными значениями г, s, s 0. Если А — индуцированный регулярный подграф из Г степени d на w вершинах, то w(k — d) s d г, v — w причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г — А смежна точно с w(k — d)/(v — w) вершинами из А. Доказательство. Это утверждение хорошо известно (см., например, 2 из [58]).
Лемма 7.2. Пусть Г является сильно регулярным графом с собственными значениями к,г 0,s — 1 кратностей l,f,g соответственно и I = v — к — 1. Допустим, что для некоторой вершины а подграф [а] сильно регулярен с матрицей смежности А\, собственными значениями ki,ri,Si 0 кратностей l,fi,gi соответственно и Г2(а) сильно регулярен с матрицей смежности А2, собственными значениями k,r2,S2 0 кратностей I,f2,g2 соответственно. Тогда выполняется одно из утверждений:
Автоморфизмы небольших сильно регулярных графов
Пусть с — вершина степени 8 в П. Если некоторая вершина из П(с) смежна с 21 вершиной из Г2 —с-1, то число ребер между Q(c) nQ — c± равно 7х + 21 = 105, противоречие. Отсюда число ребер между П(с) иП-с1 равно 7ж + 14у = 105, поэтому ж = 1, у = 7. Если П(с) является кликой, то для четырех вершин а\,..., а из П(с) степени 22 в П подграф П(аі) П [аг] содержит по 7 вершин из с и из Г — с . Поэтому Q — ([щ] U с ) содержится в rij if j] и О - с1 С [04], противоречие. Значит, П(с) является кокликой. Если П — с-1 содержит две смежных вершины е, е , имеющих степень 8 в П, то [е] П [е ] содержит не менее двух вершин из П(с), противоречие. Итак, П содержит 2 вершины с, е степени 8 и 28 вершин степени 15. Поэтому число ребер между П иГ-П равно 644, и некоторая вершина и из Г — П смежна с 10 вершинами из П. Противоречие с тем, что [и] П [и9] содержит 5 вершин из и 5 и 10 вершин из Q.
Итак, П содержит четное число t вершин а\,..., at степени 15 и 30 — t вершин степени 22, причем А = П — {ai,...,at} является кликой. Если t 26, то для 4 вершин Ь1; ...,Ь4 Е Л подграф [Ь2] содержит 7 вершин из П — hi и 12 из 19 вершин в Q(b\) — А. Противоречие с тем, что [Ьз] П [64] содержит Ь\, &2, и по 7 вершин из П - &]1 и из П(6і) — А. Значит, t 28, число ребер между П и Г — П не меньше 616, и некоторая вершина и из Г — П смежна с 9 вершинами из П. Теперь [и] П [и9] содержит 5 вершин жз w9 и 10 вершин из Q, противоречие с тем, что степень и не больше 6 + 9 + 9. Утверждение (1) доказано.
Пустьр = 5. Тогда AQ Є {4, 9,14}, [in є {2, 7,12} и П є {10,15,..., ЗО}. Ввиду леммы 9.10 число 4П + о.\(д) делится на 50. Если П = ЗО, то ввиду леммы 9.11 каждая (д)-орбита длины 5 является кликой, противоречие с тем, что 120 + ai(g) = 190 не делится на 50.
Пусть b Є П, МІ — множество вершин из П(6) степени Ы + 1 в П, ті = МІ , Nj — множество из Q — Ь±, смежных точно с 5j + 2 вершинами из П(6) и rij = iVj.
Если b — вершина степени 6 в П, то fi(6) — октаэдр и число ребер между П(6) и Q — Ь± равно 2(П — 7). Если а Є М\, то для любой вершины с Є П(6) П [а] подграф П(а) П [с] содержит 3 вершины из 6 и вершину d Є Q(a) — b L, противоречие с тем, что f2(6)n[d] 2. В случае П = 15 имеем 6ГЇІ2 = 16, противоречие. В случае П = 20 имеем 6гтт,2 + 11(6 — тг) = 26 И 777-2 = 8, Противоречие.
В случае П = 25 имеем 6??т,2 + 11?7гз + 16(6—??т-2—тяз) = 36 и 2т2+тз = 12, поэтому гтт,2 = 6. Теперь для любых двух вершин а, а Є П(6) подграф П(а) П [а ] содержит две вершины из Q — Ь±, если а, а не смежны, и одну в противном случае. Если Q — Ь± содержит вершину d степени 16 в Q, то П — (b± U d"1)! = 3. Положим П(6) П [d] = {а,а }. Если вершины а,а 128 смежны, то П(а) содержит три вершины из [d] — b± и 2 из П — (b± U d-1), противоречие с тем, что П(а) П [а ] содержит не менее двух вершин из Q — Ь±. Значит, а, а не смежны, и любая вершина из П(6) смежна с единственной вершиной из П — (b± Uб?-1). Так как число вершин из Q — Ь± степени 11 в П четно, то Q — Ь± содержит вершину е степени 6 в Q и П(е) содержит по две вершины из П(6), Q(d) — b± и из Q — (b± U d 1). Противоречие с тем, что для другой вершины е из Q — {Ъ U d ) имеем П(е) П [е ] 3.
Итак, если b — вершина степени 6 в Q, то П = 25 и Г2 состоит из вершин степеней 6 и 11.
Теперь П 10 и если П = 15, то П — регулярный граф степени 11, противоречие. Пусть П = 20. Тогда П состоит из вершин степеней 16 и 11. Если П содержит две вершины а, с степени 16, то эти вершины смежны, и П содержит а, с, 14 вершин из [а] П [с] и по одной вершине из [а] —с-1, [с] —а-1. Противоречие с тем, что для Ъ Є П —([a]U[c]) подграф П(6) содержит не менее восьми вершин из П(а) П [с]. Значит, П — регулярный граф степени 11 и /XQ = 7 (иначе для двух несмежных вершин а,Ь Є П подграф П содержит а, 6, две вершины из [а] П [6] и по девять вершин из [а] — [b], [Ь] — [а], противоречие).
Теперь число ребер между П(6) и П — б-1 равно х + 6у = 56, где ж + у = 11, поэтому х = 2 и П(6) содержит две вершины а, с степени 9. Если а, с не смежны, то П(а) П [с] содержит 10 вершин из Ь± и 2 вершины из П — (a-1 U с-1), противоречие. Значит, вершины а, с смежны, П(а) П [с] содержит либо 8 вершин из Ь± и вершину из Q — Ь±, либо 9 вершин из Ь±. В первом случае вершина е из П(6) П ([а] — [с]) смежна с 4 вершинами из П(6) П [с] и П(с) П [е] Є {5,6}, противоречие.
Пусть П = 25. Ввиду леммы 4.10 число 4П + cti(g) делится на 50, поэтому оц(д) Є {0,50}. Допустим, что орбита v g является 5-кокликой. Тогда для любой 3-коклики U из и{9) по лемме 4.11 имеем Хо(и)-\-Хз(и) = 28, причем XQ(U) иХз(11) содержит 2 вершины из v g и 25 вершин из Q. Пусть w Є Xiivr3 ). Если г 1, то w 9 содержит не менее двух вершин из X0(U), противоречие. Если г 4, то w{g) содержит не менее двух вершин из Хз(и), противоречие. Если г = 2, то пять из 10 пар вершин в ю9 смежны с вершинами из w 9 . Поэтому число орбит w 9 из Х2{иуЯ ) не больше 2. Если г = 3, то пять из 10 пар вершин в v g смежны с вершинами из w 9 . Поэтому число орбит w 9 из Х3(ю9 ) не больше 2. Противоречие с тем, что число орбит w 9 из Х2(и ) иХз(" ) равно 14.
Значит, на Г — П имеются пять ( )-орбит, являющихся кликами, пять орбит, в которых вершина смежна с ее образом под действием д, и пять орбит, в которых вершина смежна с ее образом под действием д2. Допустим, что орбита w9 является пятиугольником, и через U обозначим объединение изолированной вершины и ребра из w9 . По лемме 4 имеем Xo(U) + Хз(и) = 29, причем Xo(U) U Хз([/) содержит 25 вершин из П. Пусть w Є ХДи ). Если г 1, то г = 1 и w 9 содержит две вершины из XQ(U). Если г 4, то г = 4 и № содержит не менее двух вершин из X3(U). Если г = 2, то пять из 10 пар вершин в w9 смежны с вершинами из w 9 . Если г = 3, то пять из 10 пар вершин в v g смежны с вершинами из w 9 . Поэтому xiiw9 +Хі(и 9 ) 2. Далее, сумма числа орбит w 9 из Х2(и 9 ) таких, что w9 — [w] не является 2-путем и орбит w 9 из Xs(u 9 ) таких, что ю9 П [w] не является 2-путем, не больше 4. Итак, сумма числа орбит w{9) из Х2(« » ) таких, что ю9 — [w] является 2-путем и орбит w 9 из Х3(и 9 ) таких, что является 2-путем, не меньше 10. Про тиворечие с тем, что для 2-пути U из и{9) имеем Xo(U ) + Хз(и ) 35.
