Графы, в которых окрестности вершин – псевдогеометрические графы для 
.
, член-корреспондент РАН
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа через 
обозначим i-окрестность вершины a, то есть, подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии i от a. Положим 
, 
. Если граф 
зафиксирован, то вместо 
будем писать 
. Для множества вершин 
графа через 
обозначим 
. Если не оговорено противное, то слово «подграф» будет означать «индуцированный подграф».
Пусть F – некоторый класс графов. Граф назовем локально F-графом, если лежит в F для любой вершины a графа .
Пусть - граф, 
, число вершин в 
обозначается через 
(
), если 
находятся на расстоянии 2 (смежны) в . Далее, называется 
-подграфом (
-подграфом).
Степенью вершины называется число вершин в ее окрестности. Граф называется регулярным степени k, если степень любой вершины a из равна k. Граф назовем реберно регулярным с параметрами 
, если он содержит v вершин, регулярен степени k, и каждое его ребро лежит в треугольниках. Граф - вполне регулярный граф с параметрами 
, если он реберно регулярен с соответствующими параметрами, и содержит вершин для любых двух вершин , находящихся на расстоянии 2 в . Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2. Через 
обозначим полный многодольный граф 
с долями 
порядка 
. Если 
, то указанный граф обозначается 
.
Система инцидентности с множеством точек 
и множеством прямых 
называется 
-частичной геометрией порядка, если каждая прямая содержит 
точку, каждая точка лежит на 
прямой, любые две точки лежат не более чем на одной прямой и для любого антифлага 
найдется точно прямых, проходящих через 
и пересекающих 
(обозначение 
или 
). В случае =1 геометрия называется обобщенным четырехугольником и обозначается 
. Точечный граф геометрии определяется на множестве точек и две точки смежны, если они лежат на прямой. Точечный граф геометрии сильно регулярен с 
, 
, 
, 
. Сильно регулярный граф с такими параметрами называется псевдогеометрическим графом для .
В [1] проведена редукция классификации графов, в которых окрестности вершин являются псевдогеометрическими графами для 
к локально псевдо 
-и 
-графам. В [2] классифицированы псевдогеометрические графы для 
. В таких графах окрестность любой вершины – объединение изолированных многоугольников с числом вершин, кратным 3. В [3] классифицированы локально псевдо -графы. В данной работе классифицированы связные вполне регулярные локально псевдо - графы.
Лемма. Пусть - сильно регулярный граф с параметрами 
. Тогда выполняются следующие утверждения:
1. любой -подграф из является кокликой или объединением четырех изолированных вершин и ребра;
2. если 
- регулярный подграф из степени 6 на 
вершинах, 
,то 
, 
, в случаях 
и 
имеем 
, и 
;
3. если 
является 
-подграфом из , 
, то 
, в случае 
имеем 
, в случае 
, 
либо содержится в 
-подграфе, либо 
, 
, 
, и в случае , 
имеем 
, 
, 
, 
является 
-подграфом, каждая вершина из 
смежна с тремя вершинами степени 3 в графе и 
- регулярный граф степени 6.
Лемма. Пусть является сильно регулярным графом с параметрами , 
- трехвершинный подграф из , 
- множество вершин из 
, смежных точно с 
вершинами из , 
. Тогда выполняются следующие утверждения:
1. для двух вершин 
графа имеем 
,если не смежны, 
,если смежны;
2. 
равно 25, если является кокликой, и равно 16, если является кликой;
3. равно 20, если является 2-путем, и равно 23, если - объединение изолированной вершины и ребра.
Теорема. Пусть является связным вполне регулярным графом, в котором окрестности вершин являются псевдогеометрическими графами для . Тогда верно одно из утверждений:
1. диаметр равен 2, имеет параметры 
и собственные значения 8, -6 кратностей 100, 144;
2. 
, 
и 
;
3. 
, 
и 
.
Список литературы
1. , О графах, в которых окрестности вершин являются псевдогеометрическими графами для //Доклады академии наук 2010, т. 431, N 3, 300-304.
2. Haemers W., Spence E. The pseudo-geometric graphs for generalized quadrangles of order (3,t) //Eur. b. 2001, v. 22, N 6, 839-845.
3. О расширениях частичных геометрий, содержащих малые -подграфы //Дискр. анализ и исслед. операций 1996, т. 3, N 3, 71-83.
