• 1 Граф и его подграфы
• 2 Регулярные графы
• 3 Расширения графов
• 4 Реберные графы
• 5 Граф Шлефли
• 6 Граф системы корней
• 7 Обобщенно регулярные графы
• 8 Некоторые примеры дистанционно-регулярных графов
• 9 Редукция графа
• 10 Доминирование и неприводимость
• 11 Блоки и блок-графы

3 Основные определения и обозначения

1 Граф и его подграфы

• Неориентированный граф без петель и кратных ребер называется обыкновенным графом.

Пусть $\Gamma =\{V(\Gamma), E(\Gamma)\}$ -- конечный обыкновенный граф с множеством вершин $V(\Gamma)$ и множеством ребер $E(\Gamma)$.

• Подграфом графа $\Gamma$ называется граф $\Delta=\{V(\Delta), E(\Delta)\}$ такой, что его множество вершин $V(\Delta)$ является подмножеством множества вершин из $\Gamma$, а его множество ребер $E(\Delta)$ является подмножеством множества ребер из $\Gamma$.

• Подграф, у которого вершины смежны тогда и только тогда, когда они смежны в $\Gamma$, называется порожденным подграфом.

• Множество всех порожденных подграфов графа $\Gamma$ обозначим через ${\cal G}(\Gamma)$.

Поскольку в диссертации не рассматриваются подграфы, которые не являются порожденными, то подграфом называется только порожденный подграф.

Сокращяя обозначения, используем для множества вершин $V(\Delta)$ и для подграфа $\Delta$ один и тот же символ $\Delta$.

• Пусть $x,y$ вершины графа $\Gamma$. Последовательность вершин $x=z_1,\dots , z_k=y$ называется путем в графе $\Gamma$, если $z_i, z_{i+1}$ является ребром для всех $i=1,\dots ,k-1$.

• Расстоянием между вершинами $x,y$ графа $\Gamma$ называется наименьшая длина пути, соединяющего вершины $x,y$ в $\Gamma$. Пусть $d(x,y)$ -- расстояние между вершинами $x,y$ графа $\Gamma$. Положим $d(x,y)=\infty$, если вершины $x,y$ принадлежат различным связным компонентам графа $\Gamma$.

• Удаленностью $d(x)$ вершины $x$ в $\Gamma$ называется наибольшее расстояние $d(x,y)$, где $y$ пробегает все множество вершин из $\Gamma$.

• Радиусом графа $\Gamma$ называется наименьшая из удаленностей его вершин.

• Кликой называется полный подграф.

• Граф $\ol \Gamma$, у которого вершины смежны тогда и только тогда, когда они не смежны в $\Gamma$ называется дополнительным.

К названиям понятий, соответствующих дополнительному графу, добавляют приставку "ко".

• Кокликой называется вполне несвязный подграф.

• $n$-угольником $a_1a_2\dots a_n$ называется связный регулярный граф валентности два на $n$ вершинах, в котором $a_1a_n$, $a_ia_{i+1}$ -- ребра, $i=1,\dots ,n-1$.

• Через $K_{m_1,m_2,\dots ,m_t}$ обозначим полный многодольный граф с $t$ долями порядков $m_1,m_2,\dots ,m_t$. Если $M_1,\dots , M_t$ -- подмножества вершин полного многодольного графа $\Gamma$, соответствующие его долям, то для $\Gamma$ используем обозначение $\{M_1;M_2;\dots ;M_t\}$.

• Если $m_1=m_2=\dots =m_t$, то $K_{m_1,m_2,\dots ,m_t}$ обозначается через $K_{t\times m}$.

• Граф $K_{1,m}$ называется $m$-лапой, если $m\ge 2$.

• Граф $K_{1,1,m}$ называется $m$-короной, если $m\ge 3$.

• Для вершины $a$ графа $\Gamma$ через $\Gamma_i (a)$ обозначается подграф на множестве всех вершин, которые находятся на расстоянии $i$ от вершины $a$. Подграф $\Gamma_i (a)$ называется $i$-той окрестностью вершины $a$ в графе $\Gamma$.

• Через $\Gamma (a)$ обозначается $\Gamma_1 (a)$. Если граф $\Gamma$ зафиксирован, то $\Gamma (a)$ обозначается через $[a]$. Этот подграф называется окрестностью вершины $a$ в $\Gamma$.

• Множество всех окрестностей графа $\Gamma$ обозначим через ${\cal N}(\Gamma)$.

• Подграф на множестве $[a]\cup \{a\}$ обозначим через $a^\bot$. Подграф $a^\bot$ называется замкнутой окрестностью вершины $a$ графа $\Gamma$.

• Для подграфа $\Delta$ из $\Gamma$ и вершины $a$ из $\Delta$ обозначим через $[a]_\Delta$ окрестность $a$ в $\Delta$, а $a^\bot\cap \Delta$ через $a^\bot_\Delta$. Если $a$ не принадлежит $\Delta$, то через $[a]_\Delta$ обозначим пересечение окрестности $a$ в $\Gamma$ с $\Delta$.

• Подграф на множестве $\Gamma -a^\bot$ обозначается через $[a]'$. Этот подграф называется антиокрестностью вершины $a$ в $\Gamma$.

• Множество всех антиокрестностей графа $\Gamma$ обозначим через ${\cal A}(\Gamma)$.

• Если $a$ и $b$ -- смежные вершины графа $\Gamma$, то подграф на множестве всех вершин, которые смежны с ними обеими, называется $\lambda$-подграфом для $a, b$ и обозначается через $\Lambda _{a,b}(\Gamma)$ или просто $\Lambda _{a,b}$.

• Множество всех $\lambda$-подграфов графа $\Gamma$ обозначим через ${\cal L}(\Gamma)$.

• Если $a$ и $b$ -- несмежные вершины графа $\Gamma$ и расстояние между ними в $\Gamma$ равно 2, то подграф на множестве всех вершин, которые смежны с ними обеими, называется $\mu$-подграфом для $a, b$ и обозначается через ${\rm M}_{a,b}(\Gamma)$ или просто ${\rm M}_{a,b}$.

• Множество всех $\mu$-подграфов графа $\Gamma$ обозначим через ${\cal M}(\Gamma)$.

• Графом Тервиллигера называется неполный граф, в котором для любого $G\in {\cal M}(\Gamma)$ подграф $G$ является кликой из $\mu$ вершин для некоторого фиксированного $\mu >0$.

2 Регулярные графы

• Граф $\Gamma$ называется регулярным валентности $k$, если любой подграф из множества ${\cal N}(\Gamma)$ содержит $k$ вершин для некоторого фиксированного $k$.

• Граф $\Gamma$ называется реберно регулярным с параметрами $(v,k,\lambda)$, если $\Gamma$ -- регулярный граф на $v$ вершинах валентности $k$, в котором каждый подграф из множества ${\cal L}(\Gamma)$ имеет $\lambda$ вершин для некоторого фиксированного $\lambda$.

• Граф $\Gamma$ называется кореберно регулярным с параметрами $(v,k,\mu)$, если $\Gamma$ является регулярным графом валентности $k$, в котором любая пара несмежных вершин имеет одно и то же число $\mu$ вершин, смежных с ними обеими. Другими словами, $\Gamma$ -- $\mu$-регулярный граф диаметра два с соответствующими параметрами или $\Gamma$ -- объединение непересекающихся полных графов с числом вершин $k+1$.

• Граф $\Gamma$ называется сильно регулярным с параметрами
  
  $$(v,k,\lambda,\mu),$$
  
  
  если $\Gamma$ -- реберно-регулярный и кореберно-регулярный граф с соответствующими параметрами.

• Граф $\Gamma$ называется $\mu$-регулярным с параметрами
  
  $$(v,k,\mu),$$
  
  
  если $\Gamma$ -- регулярный граф на $v$ вершинах валентности $k$, в котором каждый подграф из множества ${\cal M}(\Gamma)$ имеет $\mu$ вершин для некоторого фиксированного $\mu >0$.

• Граф $\Gamma$ называется вполне регулярным с параметрами
  
  $$(v,k,\lambda,\mu),$$
  
  
  если $\Gamma$ -- реберно-регулярный и $\mu$-регулярный граф с соответствующими параметрами.

• Пусть $\Gamma$ -- регулярный граф валентности $k$ и диаметра $d$. Граф $\Gamma$ называется дистанционно регулярным с массивом пересечений
  
  $$i(\Gamma)=\{b_0 =k,b_1,\dots ,b_{d-1};c_1=1,c_2,\dots ,c_d\},$$
  
  
  если для каждого $i=0,1,\dots , d$ параметры
  
  $$a_i=\vert\Gamma_{i} (y)\cap \Gamma (x)\vert,$$
  
  
  
  
  $$b_i=\vert\Gamma_{i+1} (y)\cap \Gamma (x)\vert,$$
  
  
  
  
  $$c_i=\vert\Gamma_{i-1} (y)\cap \Gamma (x)\vert$$
  
  
  не зависят от выбора пары вершин $x,y$ из $\Gamma$ такой, что $d(x, y)=i$.

3 Расширения графов

• Пусть $\cal F$ -- класс графов. Граф $\Gamma$ называется локально $\cal F$-графом, если любой подграф $G$ из ${\cal N}(\Gamma)$ изоморфен некоторому графу из $\cal F$. Если класс $\cal F$ содержит только один граф $G$, то локально $\cal F$-граф называется локально $G$-графом.

• Кликовым расширением графа $\Gamma$ называется граф, полученный заменой каждой вершины $a$ из $\Gamma$ на полный подграф $C(a)$, содержащий не менее одной вершины, причем вершины из различных клик $C(a)$ и $C(b)$ смежны тогда и только тогда, когда вершины $a$ и $b$ смежны в $\Gamma$.

• Кликовое расширение графа $\Gamma$ называется $\alpha$-расширением $\Gamma$, если для любой вершины $a\in \Gamma$ подграф $C(a)$ содержит $\alpha$ вершин для некоторого фиксированного $\alpha >0$.

4 Реберные графы

• Граф $\Gamma$ называется реберным графом графа $\Delta$, если его вершинами служат ребра графа $\Delta$ и они смежны в графе $\Gamma$ тогда и только тогда, когда имеют общую вершину в $\Delta$.

• Треугольным графом $T(n)$ называется реберный граф полного графа с $n$ вершинами.

• Граф на множестве пар $X\times Y$ называется $m\times n$-графом или решетчатым графом, если $\vert X\vert=m$, $\vert Y\vert=n$, а пары $(x_1,y_1)$ и $(x_2,y_2)$ смежны тогда и только тогда, когда $x_1=x_2$, $y_1\neq y_2$ или $x_1\neq x_2$, $y_1=y_2$. Решетчатый $m\times n$-граф является реберным графом полного двудольного графа $K_{m,n}$.

• Матрицей смежности $A(\Gamma)$ графа $\Gamma$ на $v$ вершинах называется $v\times v$ матрица $A=(a_{i,j})$, строки и колонки которой занумерованы вершинами графа $\Gamma$, причем $a_{i,j}=1$, если $i,j$ -- смежные вершины и $a_{i,j}=0$, если $i,j$ -- несмежные вершины графа $\Gamma$.

• Собственными значениями графа $\Gamma$ называются собственные значения его матрицы смежности $A(\Gamma)$.

Известно, что наименьшее собственное значение треугольных и решетчатых графов равно $-2$.

Отметим некоторые свойства треугольных и решетчатых графов, которые нам необходимы.

Пусть $\Delta$ является $K_{m,n}$ графом. Перенумеруем вершины первой доли числами от $1$ до $m$, а вершины второй доли числами от $1$ до $n$. Множество всех вершин решетчатого $m\times n$-графа $\Gamma$, который является реберным графом графа $\Delta$, можно разложить в объединение $m$ максимальных непересекающихся клик $C_1,\dots , C_m$ по $n$ вершин каждая. Клика $C_i$ соответствует множеству ребер, исходящих из вершины с номером $i$ первой доли графа $\Delta$. Аналогично, множество всех вершин решетчатого графа можно разложить и в объединение $n$ максимальных непересекающихся клик $D_1,\dots , D_n$ по $m$ вершин каждая. Клика $D_j$ соответствует множеству ребер, исходящих из вершины с номером $j$ второй доли графа $\Delta$. Легко видеть, что $\vert C_i\cap D_j\vert=1$ для всех $i\in \{1,\dots m\}$, $j\in \{1,\dots n\}$, поскольку $C_i\cap D_j$ соответствует единственному ребру соединяющему вершину $i$ первой доли графа $\Delta$ с вершиной $j$ второй доли графа $\Delta$.

Таким образом, окрестность каждой вершины в решетчатом $m\times n$-графе является объединением двух изолированных клик на $m-1$ и $n-1$ вершинах соответственно, то есть она изоморфна $K_{m-1}+K_{n-1}$.

В любом решетчатом $m\times n$-графе $\Gamma$ все его подграфы из ${\cal M}(\Gamma)$ являются $2$-кокликами, а все его подграфы из ${\cal L}(\Gamma)$ являются $(m-2)$-кликами или $(n-2)$-кликами.

Треугольный граф $T(n)$ является локально решетчатым $(n-2)\times 2$ графом.

В любом треугольном графе $T(n)$ все его подграфы ${\cal M}(\Gamma)$ изоморфны $K_{2,2}$, то есть являются четырехугольниками, а все его подграфы из ${\cal L}(\Gamma)$ изоморфны $K_{n-3}+K_1$.

5 Граф Шлефли

• Обобщенным четырехугольником $GQ(s,t)$ называется конечная геометрия с множествами точек и прямых $P, L$ и отношением инцидентности $I\subseteq P\times L$ таким, что каждая точка инцидентна точно $s+1$ прямой, а каждая прямая инцидентна $t+1$ точке. При этом выполнены следующие аксиомы:

  1. Две точки инцидентны не более одной прямой.

  2. Две прямые инцидентны не более одной точке. Если две прямые инцидентны одной точке, то говорят, что эти прямые пересекаются.

  3. Для любой прямой $l\in L$ и для любой не лежащей на ней точки $p\in P$ существует только одна прямая $l'\in L$, инцидентная $p$ и пересекающая прямую $l$.

• Графом инцидентностей обобщенного четырехугольника $GQ(s,t)$ называется граф, множеством вершин которого является множество точек $GQ(s,t)$, и две вершины смежны тогда и только тогда, когда точки лежат на одной прямой.

• Граф Шлефли -- это сильно регулярный граф с параметрами $(27,16,10,8)$, который является дополнительным к графу инцидентностей обобщенного четырехугольника $GQ(2,4)$.

Известно, что граф инцидентностей обобщенного четырехугольника является сильно регуляреным графом. Обобщенный четырехугольник $GQ(2,4)$ существует и притом только один (см. теорему 1.15.2 и пример (iii) на стр. 30 монографии [6]).

Заметим, что если $\Gamma$ граф Шлефли, то он является локально $G$-графом, где $G$ -- граф Клебша. Более того, поскольку в $GQ(2,4)$ через любую точку $p$ проходит 5 прямых, на каждой из которых по две точки, отличные от точки $p$, то любая антиокрестность в графе Шлефли изоморфна графу $K_{5\times 2}$. Таким образом любой подграф из ${\cal M}(\Gamma)$ изоморфен $K_{4\times 2}$.

В следующем пункте приводится другое определение графа Шлефли.

6 Граф системы корней

• Дискретное множество векторов $L$ в ${\bf R}^n$ замкнутое относительно сложения и вычитания векторов называется целой решеткой, если скалярное произведение любых двух векторов из $L$ является целым числом.

• Целая решетка называется четной, если она состоит только из векторов четной нормы, то есть скалярное произведение $(x,x)$ является четным числом для всех $x\in L$. Заметим, что целая решетка является четной, когда она имеет базис, состоящий из векторов четной нормы.

• Корневой решеткой называется целая решетка в ${\bf R}^n$, порожденная векторами нормы 2.

Подмножество векторов данной корневой решетки $L$ образуют систему корней $\Phi$ в $V={\bf R}\otimes L$, то есть $\Phi$ является конечным множеством ненулевых векторов, порождающих $V$, таких, что выполнены следующие три условия:

$${\rm если } \lambda\in {\bf R} {\rm и } r, \lambda r \in \Phi, {\rm то } \lambda =\pm 1;$$

$${\rm если } r_1, r_2 \in \Phi, {\rm то } r_2-2\frac{(r_1,r_2)}{(r_1,r_1)}\in \Phi;$$

$$\frac{(r_1,r_2)}{(r_1,r_1)} {\rm целое число для всех } r_1, r_2 \in \Phi.$$

Векторы системы корней $\Phi$ называются корневыми векторами или корнями. Систематическое изложение теории корневых систем можно найти в книге Бурбаки [5]. Нам понадобится определение системы корней $E_8$ и соответствующего ей графа.

• Пусть $\Phi$ -- система корней, в которой все корни имеют одну и ту же норму. Графом системы корней $\Phi$ называется граф вершинами, которого являются все корни данной системы корней. Две вершины смежны тогда и только тогда, когда угол между соответствующими им векторами равен $\ds \frac{\pi}{3}$.

• Пусть $e_i$ -- вектор из ${\bf R}^n$, у которого $i$-я компонента равна $1$, а все остальные компоненты равны $0$. Система корней $E_8$ в ${\bf R}^8$ порождается всеми векторами вида $\pm e_i\pm e_j$ при $i,j\in \{1,2,\dots ,8\}$ $(i<j)$ и вектором $\ds c_8=\frac{1}{2}(e_1+\dots +e_8)$.

• Граф системы корней $E_8$ обозначим через $E_8 (1)$. Этот граф имеет 240 вершин. Причем 112 вершин вида $\pm e_i\pm e_j$ при $i,j\in \{1,2,\dots ,8\}$ $(i<j)$ и 128 вершин вида $\ds \frac{1}{2}(\pm e_1 \pm \dots \pm e_8)$, где число минусов четно.

• Граф Госсета $E_7 (1)$ является подграфом графа $E_8 (1)$ и имеет 56 вершин вида $e_i + e_j$, $c_8-e_i -e_j$, $1\le i<j\le 8$. Этому графу изоморфна каждая окрестность вершины в $E_8 (1)$. $E_7 (1)$ является графом Тэйлора. Окрестность каждой вершины в $E_7 (1)$ -- граф Шлефли.

• Граф Шлефли $E_6(1)$ является подграфом графа $E_7 (1)$ и имеет 27 вершин вида $e_i + e_7$, $e_i + e_8$, для $i\le 6$, и $c_8-e_i -e_j$, $1\le i<j\le 6$. Как уже было отмечено, он является дополнительным к графу инцидентностей обобщенного четырехугольника с параметрами $(2,4)$.

Figure: Граф Петерсена

• Граф Клебша $E_5(1)$ является подграфом графа $E_6(1)$ и имеет 16 вершин вида $e_6 + e_7$, $e_i + e_8$, для $i\le 5$, и $c_8-e_i -e_j$, $1\le i<j\le 5$. Граф Клебша -- это сильно регулярный граф с параметрами $(16,10,6,6)$. Окрестность каждой вершины в $E_5(1)$ изоморфна треугольному графу $T(5)$. Заметим, что граф $T(5)$ является дополнительным к графу Петерсена (см. рис. ).

7 Обобщенно регулярные графы

Пусть $\Gamma$ некоторый граф и $\cal F$ некоторый класс графов.

• Если для каждого графа $G$ из ${\cal F}$ не существует подграфа $H$ из ${\cal G}(\Gamma)$, изоморфного $G$, то граф $\Gamma$ называется ${\cal F}$-свободным графом.

• Если класс $\cal F$ состоит из одного графа $\Upsilon$, то ${\cal F}$-свободный граф назовем $\Upsilon$-свободным графом.

• Пусть $\Gamma$ содержит подграфы изоморфные $\Upsilon$ для некоторого графа $\Upsilon$ и $\Delta$ подграф графа $\Upsilon$. Пусть подграфы $H_1, H_2$ графа $\Gamma$, изоморфные графу $\Upsilon$, содержат общий подграф $G$, изоморфный $\Delta$. Подграфы $H_1, H_2$ назовем $G$-эквивалентными, если существует изоморфизм $\varphi$ подграфа $H_1$ на подграф $H_2$, такой что $\varphi (g)=g$ для любой вершины $g\in G$. Отношение $G$-эквивалентности является отношением эквивалентности на множестве всех подграфов из $\Gamma$, которые содержат подграф $G$ и изоморфны $\Upsilon$. Если $H$ содержит подграф $G$, то класс $\cal H$ отношения $G$-эквивалентности, содержащий $H$, назовем типом подграфа $H$ относительно $G$.

• Граф $\Gamma$ назовем $(\Delta, \Upsilon)$-однородным типа $\cal H$, если для любого подграфа $G$ из $\Gamma$, изоморфного $\Delta$, существует подграф типа $\cal H$, содержащий $G$ и изоморфный $\Upsilon$.

• Граф $\Gamma$ назовем $(\Delta, \Upsilon)$-однородным, если для любого подграфа $G$ из $\Gamma$, изоморфного $\Delta$, существует подграф, содержащий $G$ и изоморфный $\Upsilon$.

• Граф $\Gamma$ назовем $(\Delta, \Upsilon)$-регулярным типа $\cal H$, если для подграфа $G$ из $\Gamma$, изоморфного $\Delta$, число подграфов типа $\cal H$, содержащих $G$ и изоморфных $\Upsilon$, не зависит от выбора подграфа $G$.

• Граф $\Gamma$ назовем $(\Delta, \Upsilon)$-регулярным, если для подграфа $G$ из $\Gamma$, изоморфного $\Delta$, число подграфов, содержащих $G$ и изоморфных $\Upsilon$, не зависит от выбора подграфа $G$.

• $\Delta$-зависимый граф $\Gamma$ удовлетворяет $t$-вершинному условию относительно подграфа $\Delta$, если $\Gamma$ является $(\Delta, \Upsilon)$-регулярным графом для любого $t$-вершинного подграфа $\Upsilon$ из $\Gamma$, который содержит подграф, изоморфный $\Delta$.

• Граф $\Gamma$ удовлетворяет $t$-вершинному условию, если число $t$-вершинных подграфов заданного типа относительно пары различных вершин $(x,y)$ зависит только от того, является $(x,y)$ ребром или нет.

8 Некоторые примеры дистанционно-регулярных графов

Следующие примеры дистанционно-регулярных графов играют важную роль в данной работе.

• Граф на множестве $X_{1} \times \dots \times X_{n}$ называется $m_{1} \times \dots \times m_{n}$-графом, если ${\mid} X_{i} {\mid} =m_{i},$ а пары $(x_{1}, \dots ,x_{n})$ и $(y_{1}, \dots ,y_{n})$ смежны тогда и только тогда, когда существует единственное $i$ такое, что $x_{i} \neq y_{i}.$

• $m_{1} \times \dots \times m_{n}$-граф называется графом Хемминга $H(n,m)$ или $n$-мерным решетчатым графом, если $m_{i}=m$ для всех $i$.

Пусть $V$ является $n$-мерным векторным пространством над конечным полем $F$.

• Графом Грассмана для $m$-подпространств из $V$ называется граф $\left[V\atop m\right]$ с множеством вершин, равным множеству всех подпространств размерности $m$ из $V$, причем две вершины $A, B$ смежны тогда и только тогда, когда $dim(A\cap B) = m-1$.

• Если $X$ -- конечное множество, то графом Джонсона для $m$-подмножеств из $X$ называется граф с множеством вершин, равным множеству $\left(X\atop m\right)$ всех $m$-элементных подмножеств из $X$, причем две вершины $a, b$ смежны тогда и только тогда, когда $\vert a\cap b\vert = m-1$. Если множество $X$ состоит из $n$ элементов, то такой граф обозначим через $J(n,m)$. Заметим, что граф $J(n,2)$ совпадает с треугольным графом $T(n)$.

• Пусть $\rho$ -- некоторое разбиение множества вершин графа $\Gamma$ на подмножества. Частным $\overline\Gamma = \Gamma/\rho$ для графа $\Gamma$ по разбиению $\rho$ называется граф на фактор-множестве по $\rho$ множества вершин $\Gamma$, в котором две вершины $\overline a, \overline b$ смежны только, если $a\neq b$ и граф $\Gamma$ содержит ребро, которое соединяет некоторую вершину из класса $\overline a$ с некоторой вершиной из класса $\overline b$.

• Пусть $n=2m$ и $\rho$ является разбиением множества вершин графа Джонсона $J(2m,m)$ на двухэлементные классы, содержащие $m$-элементное подмножество и его дополнение в $X$. Частным графа Джонсона называется граф $J(2m,m)/ \rho$.

• Ректаграфом называется связный граф без треугольников, в котором любой путь длины 2 лежит в единственном четырехугольнике.

Figure: Граф икосаэдра

• Графом Тэйлора называется вполне регулярный граф диаметра 3, в котором множество вершин совпадает с $a^\bot \cup b^\bot$ для любых двух вершин $a, b$, находящихся на расстоянии 3.

• Граф икосаэдра -- это граф Тэйлора, в котором окрестность любой вершины является пятиугольником (Рис. ).

9 Редукция графа

• Пусть $\Delta$ подграф графа $\Gamma$. Тогда через $\Delta^\bot$ обозначим подграф $\ds \bigcap _{a\in\Delta} a^\bot$.

• Ядром подграфа $\Delta$, содержащего более одной вершины, называется подграф $K(\Delta)=\Delta^\bot \cap\Delta$.

• Ядром вершины $a$ называется подграф $K(a)=\{x\in \Gamma \vert x^\bot = a^\bot\}$. Понятно, этот подграф совпадает с $(a^\bot)^\bot$.

• Число вершин в $K(a)$ обозначается через $\hat{a}$.

• Вершину $a$ назовем редуцированной, если $K(a)$ состоит из единственной вершины $a$, то есть $\hat{a}=1$.

• Граф $\Gamma$ называется редуцированным, если все его вершины редуцированые.

• Пусть на графе $\Gamma$ задано отношение эквивалентности $x\equiv y$ такое, что $x\equiv y$ тогда и только тогда, когда $x^\bot = y^\bot$. Редукцией графа $\Gamma$ называется фактор-граф $\overline{\Gamma}$ графа $\Gamma$ по отношению $\equiv$.

10 Доминирование и неприводимость

• Если $X$ -- некоторое множество вершин графа $\Gamma$, то через $N_\Gamma(X)$ обозначим множество $\ds\bigcup_{x\in X} [x]$, то есть множество вершин, которые смежны хотя бы с одной вершиной из $X$. Через $\ds N_\Gamma[X]$ обозначим множество $\bigcup_{x\in X} x^\bot$. Если граф $\Gamma$ зафиксирован, то положим $N_\Gamma(X)=N(X)$ и $N_\Gamma[X]=N[X]$. Заметим, что если $X$ содержит только одну вершину $x$, то $N(X)= [x]$ и $N[X]=x^\bot$.

• Если нужно подчеркнуть, что рассматривается порожденный подграф графа $\Gamma$ на некотором множестве его вершин $X$, то обозначим его через $\Gamma\langle X\rangle$. Если граф $\Gamma$ зафиксирован, то $\Gamma\langle X\rangle=\langle X\rangle$.

• Некоторое множество $X$ вершин из $\Gamma$ называется доминирующим, если $N_\Gamma[X] =V(\Gamma)$.

• Минимальное число элементов в доминирующем множестве вершин графа $\Gamma$ обозначается через $\gamma (\Gamma)$ и называется нижним параметром доминирования графа $\Gamma$.

• Если $x$ -- вершина некоторого подмножества $X$ из $V(\Gamma)$, то множество $PN(x) =x^\bot\setminus N[X\setminus \{x\}]$ называется $X$-приватной окрестностью вершины $x$, а его элементы -- $X$-приватными соседями для $x$.

• Вершина $x$ из $X$ неприводима относительно $X$, если ее $X$-приватная окрестность не является пустым множеством, в противном случае $x$ называется приводимой относительно $X$.

• Множество вершин $X$ называется неприводимым в $\Gamma$, если все его вершины неприводимы относительно $X$ в $\Gamma$.

• Среди всех максимальных неприводимых множеств выберем множество $X$, содержащее наименьшее число вершин. Число вершин в $X$ назовем нижним параметром неприводимости для графа $\Gamma$ и обозначим через $ir(\Gamma)$.

11 Блоки и блок-графы

Вершина $v$ связного графа $\Gamma$ называется точкой сочленения, если если $\Gamma -v$ является несвязным графом.

Связный граф называется блоком, если он не имеет точек сочленения.

Блоком графа $\Gamma$ называется связный подграф $\Gamma$, который не имеет точек сочленения и максимален относительно свойства "не иметь точек сочленения". Если блок не является ребром, то это максимальный 2-связный подграф графа $\Gamma$.

Блок-граф -- это граф, в котором все блоки являются кликами.

Через ${\cal B}(\Gamma)$ обозначим множество всех блоков графа $\Gamma$, а через ${\cal C}(\Gamma)$ -- множество всех точек сочленения для $\Gamma$.

Граф $\Gamma$ называется кликово-сочлененным, если множество вершин из $B\cap {\cal C}(\Gamma)$ образуют клику для каждого блока $B$ из ${\cal B}(G)$.

Заметим, что любой блок-граф является кликово сочлененным графом.