Графы, в которых окрестности вершин – псевдогеометрические графы для



Скачать 38.73 Kb.
Дата11.10.2012
Размер38.73 Kb.
ТипДокументы
Графы, в которых окрестности вершин – псевдогеометрические графы для .
А.К. Гутнова, член-корреспондент РАН А.А. Махнев
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины 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. J. Comb. 2001, v. 22, N 6, 839-845.

  3. Махнев А.А. О расширениях частичных геометрий, содержащих малые -подграфы //Дискр. анализ и исслед. операций 1996, т. 3, N 3, 71-83.

Похожие:

Графы, в которых окрестности вершин – псевдогеометрические графы для iconИ. Н. Белоусов, Н. Д. Зюляркина, А. А. Махнев, М. С. Нирова
...
Графы, в которых окрестности вершин – псевдогеометрические графы для iconЛитература brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs, Springer-Verlag. Berlin Heidelberg New Yor
Дистанционно регулярные графы, в которых окрестности вершин изоморфны графу Хофмана-Синглтона: редукция к графам Тервиллигера
Графы, в которых окрестности вершин – псевдогеометрические графы для iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Графы, в которых окрестности вершин – псевдогеометрические графы для iconПояснительная записка: Требования к студентам : курс «Дискретные математические модели»
ЕН. Ф. 01. Плоские графы; эйлеровы графы; гамильтоновы графы; орграфы; сетевые графики; сети Петри
Графы, в которых окрестности вершин – псевдогеометрические графы для iconВ вопроснике просьба только пометить указанный ниже номер графы. Не указывайте полного названия графы

Графы, в которых окрестности вершин – псевдогеометрические графы для iconПлоские графы и теорема Рамсея
...
Графы, в которых окрестности вершин – псевдогеометрические графы для iconЛекция №8 Теоретико-множественное определение графа Раздел Графы
Наглядное представление о графе можно получить, если представить себе некоторое множество точек плоскости X, называемых вершинами,...
Графы, в которых окрестности вершин – псевдогеометрические графы для iconСогласно договорам услуги по шеф-надзору измеряются в днях, часах. Шеф-монтаж, согласно договорам, выполняется поэтапно, без указания единиц измерения. Как заполнять графы 2, 2а, 3 счета-фактуры на шеф-надзор, шеф-монтаж
Как заполнять графы 2, 2а, 3 счета-фактуры на шеф-надзор, шеф-монтаж, а также на комиссионное вознаграждение?
Графы, в которых окрестности вершин – псевдогеометрические графы для iconТема графы

Графы, в которых окрестности вершин – псевдогеометрические графы для iconПриложение №3 Список кодов и данных, необходимых для заполнения графы 20, согласно правилам incoterms 2000

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org