сти на множестве вершин графа. Антиподальный граф диаметра 3 на 12 вершинах, в котором окрестность любой вершины - пятиугольник, называется графом икосаэдра. Антиподальный граф диаметра 3 на 56 вершинах, в котором окрестность любой вершины - граф Шлефли, называется графом Госсета. Граф Тервиллигера -это неполный граф, в котором ц-подграфы являются кликами одного порядка.
Цель сообщения - получение характеризаций некоторых классов дистанционно регулярных графов (в частности, графов знакопеременных форм и графов квадратичных форм над полем из двух элементов) с помощью довольно общих условий регулярности и некоторых запрещенных подграфов. Как правило, ранее такие характери-зации были получены по массивам пересечений (см. [1]). В работах [2, 3] получена классификация графов без корон, в которых ц-подграфы являются регулярными графами диаметра 2 заданной положительной степени а. С помощью этих результатов доказаны следующие две теоремы.
Теорема 1. Пусть Г - связный граф без 3-корон, в котором любой ц-подграф А состоит из V вершин, V > 1 и |А(х) п А(;у)| = X' > 0 для любых смежных вершин х, у е А. Если окрестность некоторой вершины из Г является графом Тервиллигера, то Г является либо кликовым (X' + 2)-расширением (т X п)-решетки, либо графом Тервиллигера одного из следующих типов:
(1) кликовое расширение 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;
(2) кликовое расширение графа А, где А содержит 5-клику и 5 или 5 - 1 вершин степени 1, смежных с различными вершинами этой клики;
(3) кликовое расширение графа икосаэдра или графа без 3-лап с ц = 1.
Теорема 2. Пусть Г - связный граф без 3-корон, в котором каждый ц-подграф А является реберно-регулярным графом с параметрами (V', к, X') и окрестностями вершин диаметра 2. Если 0 < X' < к'—1, то либо окрестности вершин в Г являются сильно регулярными графами без 3-коклик, либо Г - локально А-граф, где А - один из следующих графов:
(1) треугольный граф Т(п), п >6, или граф Шлефли;
(2) частное графа Джонсона 1 (10, 5) или половинный граф свернутого 10-куба;
(3) граф Грассмана 1^ (п, 2), где п > 4.
Для восстановления окрестностей вершин необходимо следующее утверждение, доказанное в [2] для графов без 3-лап.
Предложение 1. Если Г - связный слабо редуцированный граф без корон, в котором
ц-подграфы регулярны степени а > 0, то Г является редуцированным графом или пятиугольной пирамидой.
Если Г - связный граф, в котором окрестность любой вершины является графом Грассмана 1д(п, 2), то каждый ц-подграф из Г является локально ((д +1) X (д + 1))-решеткой.
Теорема 3. Пусть Ъ - связный локально ((д + 1) X (д + 1))-подграф графа Грассмана Г = 1д(п, 2), отвечающего линейному пространству V.
Тогда д = 2 и выполняется одно из следующих утверждений:
1) граф Ъ является дополнительным для (4 X 4)-решетки и содержится в подграфе из Г, отвечающем четырехмерному подпространству из V;
2) граф Ъ является графом Джонсона 1(6, 3) и содержится в подграфе из Г, отвечающем либо четырехмерному, либо пятимерному подпространству Ж из V, причем в последнем случае
подграф Ъ п
является треугольным графом
Т(5) для любой гиперплоскости и из Ж.
Доказательство теоремы 3 опирается на следующее
Предложение 2. Пусть Г - граф Грассмана 1д(4, 2), содержащий связный локально ((д +1) X X т)-подграф Ъ, где 2 < т < д.
Тогда т = д = 2 и Ъ - треугольный граф Т(5).
Следствие. Пусть Г - связный граф без 3-корон, в котором каждый ц-подграф А является связным реберно-регулярным графом с параметрами (V', к, X') и окрестностями вершин диаметра 2. Если 0 < X' < к - 1, то выполняется одно из следующих утверждений:
1) либо Г является графом Шлефли или графом Госсета, либо граф Г имеет параметры ((г2 + 3г)2, г3 + 3г2 + г, 0, г2 + г) для некоторого г > 1;
2) каждый ц-подграф является октаэдром и Г - половинный граф ректаграфа с с3 = 3;
3) окрестность каждой вершины в Г - половинный граф свернутого 10-куба;
4) Г является локально грассмановым графом и либо
(1) ц = 16, п = 4 и Г - антиподальный граф диаметра 3 на 72 вершинах, либо
(п) ц = 20, и если для любой вершины а графа Г граф Г2(а) является регулярным степени 15 ■ 2п- 1 - 105, то Г имеет накрытие, являющееся графом А^(п, 2) знакопеременных форм или графом Quad(n - 1, 2) квадратичных форм.
Доказательство следствия. Пусть Г - связный граф из заключения теоремы 2. Если
ХАРАКТЕРИЗАЦИЯ НЕКОТОРЫХ ДИСТАНЦИОННО РЕГУЛЯРНЫХ ГРАФОВ
585
окрестность каждой вершины в графе Г является сильно регулярным графом без 3-коклик, то выполняется утверждение 1). Если Г является локально графом Шлефли, то Г - граф Госсета. Если Г является локально треугольным графом, то каждый |-подграф состоит из изолированных октаэдров и Г - половинный граф ректаграфа с с3 = 3. По теореме из [4] не существуют локально 1 (10, 5) графы. Пусть Г - связный граф, в котором окрестность любой вершины является графом Грассмана ёч(п, 2). По теореме 3 имеем q = 2 и либо каждый |-подграф из Г является дополнительным для (4 х 4)-решетки, либо каждый |-под-граф из Г является графом Джонсона 1(6, 3). В первом случае п = 4 и Г - антиподальный граф диаметра 3 на 72 вершинах. Во втором случае при дополнительном предположении, что для любой вершины а графа Г граф Г2(а) является регулярным степени 15 ■ 2п - 1 - 105, в [5] доказано, что Г является накрытием графа АШП, 2) знакопеременных форм или графа Quad(n, 2) квадратичных форм. Следствие доказано.
Поскольку доказательства теорем 1-3 весьма громоздки, мы ограничимся доказательством предложения 1. Мы докажем, что если Г является слабо редуцированным, но не редуцированным графом без корон, в котором |-подграфы регулярны степени а, а > 0, то Г является кликовым расширением пятиугольной пирамиды. Допустим, что Ь1 с а1 для некоторых вершин а, Ь е Г. Ясно, что [Ь] не содержит 3-коклик (иначе Г содержит корону). Среди вершин х со свойством х1 с а1 выберем вершину Ь наибольшей степени. Ввиду предложения [3] можно считать, что Г содержит 3-лапу. Мы докажем три леммы, с помощью которых завершим доказательство предложения 1.
Лемма 1. Если вершина х из [Ь] - {а} смежна с вершиной вне а1, то [х] не пересекает [а] - Ь1, далее подграф [Ь] не является кликой.
Доказательство. Пусть вершина х смежна с вершиной с вне а1 и вершиной ё из [а] - Ь1. Если вершины с, ё смежны, то в графе [Ь] п [с] степень вершины х равна а. Противоречие с тем, что в графе [а] п [с] вершина х смежна еще с ё. Значит, любая вершина из [х] - а1 не смежна ни с одной из вершин в ([х] п [а]) - Ь1. Тогда [х] п [с] п [ё] не пересекает Г - а1 и [а] - Ь1. Так как а > 0, то [х] п [с] п [ё] содержит вершину у из [Ь]. Противоречие с тем, что тогда Г содержит корону {х; у;
b, с, ё}. Пусть [Ь] - клика. Тогда для любой вершины ё из [а] - Ь1 подграф [Ь] п [ё] является (а + 1)-кликой. Пусть х е ([Ь] п [ё]) - {а}. В силу выбора вершины Ь подграф [х] не содержится в а1, противоречие с первым утверждением леммы.
Лемма 2. Для любых двух несмежных вершин
c, ё из [Ь] подграфы [с] и [ё] пересекают [а] - Ь1.
Доказательство. Допустим, что с, ё - несмежные вершины из [Ь] и [ё] не пересекает [а] - Ь1. Если е е ([а] п [с]) - Ь1, то подграф [ё] п [е] содержит а + 1 вершин из а1, попадающих в [Ь]. Противоречие с тем, что в графе [Ь] п [е] вершина а смежна еще с вершиной с. Значит, и [с] не пересекает [а] - Ь1. Для е е [а] - Ь1 по первому утверждению леммы 1 подграф [с] п [е] является (а + 1)-кликой из [Ь]. Симметрично подграф [ё] п [е] является (а + 1)-кликой из [Ь], причем [с] п [ё] п [е] содержит единственную вершину а. Противоречие с тем, что тогда степень а в графе [Ь] п [е] равна 2а.
Лемма 3. Выполняются следующие утверждения.
1) [х] с [а] для любой вершины х е Ь1 и а -единственная среди вершин х из Г со свойством Ь1 с х1;
2) [Ь] - {а} является кликовым (а - 1)-расширением пятиугольника;
3) а = 2 и каждая вершина из [а] - Ь1 смежна с ребром пятиугольника [Ь] - {а}.
Доказательство. Заметим, что ввиду лемм 1, 2 окрестности любых двух несмежных вершин с, ё из [Ь] попадают в а1. Если же Ь1 с е1 для некоторой отличной от а вершины е, то по выбору вершины Ь подграф [е] содержит вершину / вне а1. В этом случае [Ь] п [/] является (а+1)-кликой, состоящей из вершин е таких, что Ь1 с е1. Противоречие с тем, что тогда Г содержит (а + 1)-корону {[Ь] п [/]; с, ё, /}. Утверждение 1) доказано.
По утверждению 1) для любых двух несмежных вершин с, ё из [Ь] подграф [с] п [ё] является (а + 1)-кликой из а1. Тогда [с] п [ё] с Ь1. Таким образом, [Ь] является графом Тервиллигера. По теореме 1 из [3] граф [Ь] является кликовым расширением 2-пути или пятиугольной пирамиды. В первом случае по утверждению 1) [Ь] - {а} состоит из двух изолированных клик и а = 1. Отсюда [а] является графом Тервиллигера диаметра 2 без 3-лап с | = 1. Снова по теореме 1 из [3] граф [а] является пятиугольником {Ь, с, е, /, ё}. Если [е] - а1 содержит вершину g, то вершина е изолирована в [с] п [#], противоречие. Итак, Г = а1. Противоречие с тем, что Г содержит 3-лапу. Значит, граф [Ь] - {а} является кликовым расширением пятиугольника. Если с, ё - две несмежные вершины из [Ь], то степень Ь в графе [с] п [ё] равна а, поэтому граф [Ь] - {а} является (а - ^-расширением пятиугольника. Утверждение 2) доказано.
Пусть/е [а] - Ь1. Тогда [/] п [Ь] является (а + 1)-кликой из а1. Поэтому [/] содержит вершины с, ё из двух разных (а - 1)-клик графа [Ь] - {а}. Если / не смежна с вершиной е из (а - 1)-клики, содержащей ё, то [с] содержит 3-коклику / е, g, где
g е ([&] п [с]) - [<], противоречие. Таким образом, [/] содержит две разные (а - 1)-клики графа [Ь] - {а}. Поэтому |[б] п [/]| = 2а - 1 = а + 1 и а = 2. Лемма доказана.
Завершим доказательство предложения 1. По лемме 3 подграф [Ь] является пятиугольной пирамидой с вершиной а. Пусть cdefg -это 5-цикл из [Ь], и е [а] - Ь±. Ввиду леммы 3 без ограничения общности и смежна с g, с. Тогда [и] п [ СС] содержит а, с и вершину, смежную с с, <. Симметрично [и] п [ / ] содержит а, g и вершину, смежную с/, g. Наконец, [и] п [е] содержит а и две вершины из [а] - Ь±. Значит, степень каждой вершины и е [а] - Ь± не меньше
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.