2 Содержание работы

Если $x,y$ пара вершин графа $\Gamma$, которые находятся на расстоянии 2 друг от друга, то подграф на множестве общих смежных с ними вершин называется $\mu$-подграфом графа $\Gamma$.

Графы без 3-лап с несвязными $\mu$-подграфами были изучены в 1994 году А.Е. Брауэром и М. Нуматой [7]. Теорема А.Е. Брауэра и М. Нуматы [7] утверждает, что конечными графами без 3-лап, у которых все $\mu$-подграфы несвязны, являются решетчатые $m\times n$-графы и $N_m$-графы. Пусть $\{0,1,\dots ,3m\}$ множество вершин $N_m$-графа. Тогда вершины $i,j$, где $i<j$, смежны в $N_m$-графе тогда и только тогда, когда $j-i\not\equiv 2({\rm mod} 3)$. Понятно, что $N_m$-графы не содержат $3$-коклик.

В графе с несвязными $\mu$-подграфами любой подграф, изоморфный $K_{1,2}$, содержится в подграфе, изоморфном $K_{2,2}$, то есть в $C_4$. Такие графы мы будем называть $(K_{1,2}, K_{2,2})$-однородными графами. Следовательно, граф, у которого все $\mu$-подграфы несвязны, является $(K_{1,2}, K_{2,2})$-однородным графом.

Следующая теорема, которая обобщает теорему А.Е. Брауэра и М. Нуматы в том случае, когда граф содержит $3$-коклику, доказывается в первой главе диссертации [45]. Для того, чтобы сформулировать теорему, нам понадобится понятие кликового расширения графа. Кликовым расширением графа $\Gamma$ называется граф, полученный заменой каждой вершины $a$ из $\Gamma$ на полный подграф $C(a)$, содержащий не менее одной вершины, причем вершины из различных клик $C(a)$ и $C(b)$ смежны тогда и только тогда, когда вершины $a$ и $b$ смежны в $\Gamma$. Кликовое расширение графа $\Gamma$ называется $\alpha$-расширением $\Gamma$, если для любой вершины $a\in \Gamma$ подграф $C(a)$ содержит $\alpha$ вершин для некоторого фиксированного $\alpha >0$. Заметим, что если граф $\Gamma$ не содержит 3-лап, то и любое его кликовое расширение не содержит 3-лап.

ТЕОРЕМА 1.

Пусть связный граф $\Gamma$ содержит $3$-коклику и не содержит $3$-лап. Если любой подграф из $\Gamma$, изоморфный $K_{1,2}$, содержится в подграфе, изоморфном $K_{2,2}$, то $\Gamma$ является кликовым расширением одного из следующих графов:

$(1)$ решетчатый $m\times n$-граф при $m\ge 3$, $n\ge 3$;

$(2)$ треугольный граф $T(n)$ при $n\ge 6$;

$(3)$ граф Шлефли.

Для удобства обозначим через $\Xi$ класс графов, который состоит из $m\times n$-графов при $m\ge 3$, $n\ge 3$, треугольных графов $T(n)$ при $n\ge 6$ и графа Шлефли. В теореме 1 из работы [29] М. Нуматой была получена классификация реберно-регулярных графов, которые не содержат 3-лап и содержат $3$-коклику. Оказалось, что если такой граф имеет диаметр 2, то он является или графом из класса $\Xi$ или графом $P_n$ при $n\ge 2$, который имеет $5n^2$ вершин.

Следующая теорема, которая является аналогом этого результата для кореберно-регулярных графов без 3-лап, также доказывается в первой главе диссертации [53].

ТЕОРЕМА 2.

Пусть $\Gamma$ -- кореберно-регулярный граф без $3$-лап. Тогда $\Gamma$ является либо дополнительным графом к регулярному графу без треугольников, либо $\alpha$-расширением $(\alpha \ge 1)$ одного из следующих графов:

$(1)$ вполне несвязный граф с числом вершин $m$ $(m \neq 2)$;

$(2)$ решетчатый $m\times n$-граф при $m\ge 3, n\ge 3$;

$(3)$ треугольный граф $T(m)$ при $m\ge 6$;

$(4)$ граф Шлефли.

В теореме 2 работы [29] М. Нуматой получена классификация реберно-регулярных графов диаметра не менее 3, которые не содержат 3-лап и содержат $3$-коклику. Он показал, что либо все $\mu$-подграфы такого графа имеют не более 2 вершин, либо граф изоморфен графу икосаэдра.

Полученные результаты служат основой для исследования графов без 3-лап с более слабыми условиями регулярности во второй главе диссертации.

Пусть $x,y$ пара вершин графа $\Gamma$, которые находятся на расстоянии 2 друг от друга. Обозначим число вершин $\mu$-подграфа для $x,y$ через $\mu (x,y)$. Если все $\mu$-подграфы графа $\Gamma$ имеют одинаковое число вершин, то есть $\mu (x,y)=\mu$, то это число называется параметром $\mu$ графа $\Gamma$. Понятно, что если граф имеет параметр $\mu$, то $\mu$ не меньше 1. Если граф $\Gamma$ имеет параметр $\mu$, но его значение неизвестно, то мы говорим, что $\Gamma$ имеет равномощные $\mu$-подграфы. По определению сильного графа, любая пара несмежных вершин в нем имеет одно и то же число общих соседей. Это условие автоматически приводит к тому, что либо диаметр сильного графа равен 2 и он имеет равномощные $\mu$-подграфы, либо число общих соседей любой пары несмежных вершин в нем равно 0. Таким образом, условие равномощности $\mu$-подграфов значительно ослабляет соответствующее условие в определении сильного графа.

Вторая глава диссертации посвящена классификации графов без 3-лап с равномощными $\mu$-подграфами без ограничения на диаметр графа. В первом параграфе главы 2 рассматриваются регулярные графы без 3-лап с равномощными $\mu$-подграфами, а во втором параграфе исследуются нерегулярные графы из этого класса. Изучение класса графов без 3-лап с равномощными $\mu$-подграфами самая трудная и большая по объему часть работы. Оказалось, что сильное влияние на строение графа оказывает наличие или отсутствие в графе порожденных 4-циклов. Графы без 4-циклов с равномощными $\mu$-подграфами изучал П. Тервиллигер в [38]. Он доказал реберную регулярность таких графов при некоторых дополнительных условиях, в частности, для регулярных графов диаметра 2. Графы без порожденных 4-циклов с равномощными $\mu$-подграфами мы будем называть графами Тервиллигера.

Следующая теорема классифицирует регулярные графы Тервиллигера без 3-лап [54].

ТЕОРЕМА 3.Связный регулярный граф Тервиллигера без 3-лап является $\alpha$-расширением одного из следующих графов:

$(1)$ граф без $3$-лап с $\mu = 1$,

$(2)$ граф икосаэдра.

Примеры регулярных графов без 3-лап с $\mu = 1$ имеются среди графов вершин и ребер полуправильных многогранников. Граф усеченного тетраэдра является $\mu$-регулярным с $\mu = 1$, но не реберно-регулярным графом. Граф кубооктаэдра, наоборот, является реберно-регулярным графом без 3-лап, но не является $\mu$-регулярным графом. В следующей теореме классифицированы связные $\mu$-регулярные графы без 3-лап [54].

ТЕОРЕМА 4.

Связный $\mu$-регулярный граф $\Gamma$ без $3$-лап либо является графом Тервиллигера, либо имеет диаметр $2$.

Теперь строение связных $\mu$-регулярных графов определяют теорема 2 и теорема 3, поскольку в них определены графы Тервиллигера без $3$-лап и кореберно-регулярные графы без 3-лап.

В следующей теореме мы не предполагаем регулярности графа, и, таким образом, она завершает классификацию графов Тервиллигера без 3-лап [55]. Эта теорема расширяет теорему Тэйлора-Левингстона [37]. Через $a^\bot$ обозначим порожденный подграф, состоящий из вершины $a$ и всех смежных с ней вершин. Через $\Gamma^\bot$ обозначим подграф $$\bigcap _{a\in\Gamma} a^\bot$$.

ТЕОРЕМА 5.Пусть $\Gamma$ -- связный граф Тервиллигера без $3$-лап. Тогда либо граф $\Gamma$ является $\alpha$-расширением графа икосаэдра, либо подграф на множестве всех вершин с некликовыми окрестностями из $\Gamma -\Gamma^\bot$ является пустым, кликой или $\alpha$-расширением связного графа с $\mu = 1$.

При условии, что граф содержит 3-коклику, удается получить полную классификацию не только графов Тервиллигера без 3-лап, но и всех графов без 3-лап с равномощными $\mu$-подграфами [55].

ТЕОРЕМА 6. Пусть $\Gamma$ -- связный граф без $3$-лап, содержащий $3$-коклику. Пусть также все $\mu$-подграфы из $\Gamma$ имеют одинаковое число вершин. Тогда либо $\Gamma$ имеет диаметр больше двух и является графом из заключения теоремы 5, либо граф $\Gamma$ является $\alpha$-расширением одного из следующих графов:

$(1)$ решетчатый $m\times n$-граф при $m\geq 3$, $n\geq 3$;

$(2)$ треугольный граф $T(m)$ при $m\geq 6$;

$(3)$ граф Шлефли.

Следующая теорема посвящена описанию графов без 3-лап с регулярными $\mu$-подграфами одинаковой ненулевой валентности. Регулярный граф называется редуцированным, если для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ состоит из единственной вершины $a$. В статье [27] А.А. Махнев перенес это понятие на класс всех графов. Произвольный граф $\Gamma$ называется редуцированным, если для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot \subseteq x^\bot \}$ состоит из единственной вершины $a$. Легко видеть, что в классе регулярных графов оба определения эквивалентны.

В [27] А.А. Махнев классифицировал редуцированные графы без 3-лап с регулярными $\mu$-подграфами валентности $\alpha$, где $\alpha >0$. Мы докажем, что если $\Gamma$ является графом без 3-лап с регулярными $\mu$-подграфами одинаковой валентности $\alpha$, где $\alpha >0$, и для любой вершины $a$ из $\Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ совпадает с $\{a\}$, то и множество $\{x\in \Gamma \vert a^\bot \subseteq x^\bot \}$ состоит из единственной вершины $a$. Следующая теорема [43,44] усиливает основной результат из [27].

ТЕОРЕМА 7.

Пусть $\Gamma$ -- связный граф, который не содержит $3$-лап и содержит $3$-коклику и выполнены следующие условия:

$(a)$ все $\mu$-подграфы из $\Gamma$ являются регулярными графами одинаковой валентности $\alpha$ для некоторого числа $\alpha >0$;

$(b)$ для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ состоит из единственной вершины $a$.

Тогда граф $\Gamma$ является треугольным графом $T(n)$ при $n\geq 6$, графом икосаэдра или графом Шлефли.

В работе [19] М.Д. Хестенс и Д.Г. Хигман отметили другой момент, касающийся связи между теорией графов и теорией транзитивных групп подстановок. Пусть $G$ -- транзитивная группа подстановок на множестве $\Omega$. Тогда орбиты группы $G$ на множестве $\Omega\times\Omega$ называются орбиталами, а их число -- рангом группы $G$. Каждый орбитал $\Delta$ является либо симметричным, либо строго антисимметричным. В первом случае он определяет обыкновенный граф с множеством вершин $\Omega$ и множеством ребер $\Delta$. Во втором случае орбитал имеет симметричную ему пару $\Delta'=\{(y,x)\vert (x,y)\in \Delta\}$ и определяет ориентированный граф. Известно, что группа $G$ обладает симметричным орбиталом тогда и только тогда, когда ее порядок является четным числом [40].

Если группа $G$ имеет ранг 3, то оба орбитала, отличные от диагонали $\{(x,x)\vert x\in \Omega\}$, являются симметричными и определяют пару дополнительных сильно регулярных графов. Такой сильно регулярный граф называется графом ранга 3. В настоящее время с использованием классификации конечных простых групп получено полное описание групп и графов ранга 3 ([9], [25], [2], [26], [24]).

Много работ посвящено изучению транзитивных групп подстановок без ограничений на их ранг и графов, которые определяются их орбиталами. В программном комплексе GAP [32] имеется специальная инструкция EdgeOrbitGraph, которая позволяет строить граф по орбиталу заданной транзитивной группы подстановок. При помощи этой инструкции автором найден пример дистанционно-транзитивного локально без 3-лап графа с несвязными окрестностями вершин. Этот граф является локально $4L(K_{4,2})$-графом, то есть графом, любая окрестность вершины которого является объединением четырех решетчатых $4\times 2$-графов. Он получается из наименьшего орбитала группы Хигмена-Симса при представлении ее как транзитивной группы подстановок, действующей на классе центральных инволюций.

С другой стороны, интересен следующий, связанный с данным, вопрос. А именно, какими свойствами должен обладать граф, чтобы множество его ребер оказалось орбиталом для группы подстановок, действующей транзитивно на его вершинах (граф, изоморфный такому графу, мы назовем орбитальным)? Этот вопрос тесно связан с вопросом изучения групп автоморфизмов графов. В работах [14], [15] Х. Еномото получил характеризацию графов Хэмминга как орбитальных графов для транзитивных групп подстановок с определенными ограничениями на их подстепени. Первая теорема третьей главы диссертации, опубликованная в [54], усиливает результат Х. Еномото. Для ее формулировки нам понадобится определение отделимого графа. Граф $\Gamma$ назовем отделимым, если для любой вершины $a$ из $\Gamma$ подграф $\Gamma_{2}(a)$ содержит вершины $b,c$ на расстоянии 2 в $\Gamma_{2}(a)$ и $\mu$-подграф $[b]\cap [c]$ для любой такой пары не пересекает $[a]$.

ТЕОРЕМА 8.

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

$(1)$ граф Хемминга $H(n,m)$ при $m\ge 3, n\ge 2$;

$(2)$ треугольный граф $T(m)$ при $m\ge 6$;

$(3)$ граф Шлефли;

$(4)$ граф икосаэдра.

Используя классификацию реберно-регулярных графов без 3-лап [29], М. Нумата в работе [30] получил характеризацию графов Грассмана и Джонсона как графов локально без 3-лап, в которых все $\mu$-подграфы являются изоморфными реберно-регулярными графами диаметра 2. Заметим, что если граф $\Gamma$ удовлетворяет условию теоремы М. Нуматы, то из последнего условия на все $\mu$-подграфы графа $\Gamma$ непосредственно следует реберная регулярность самого $\Gamma$.

Наша следующая цель получить классификацию локально без 3-лап графов с более слабым условием на $\mu$-подграфы, которое не влечет даже регулярности графа. Это стало возможно благодаря классификации графов без 3-лап с равномощными $\mu$-подграфами. С помощью этой классификации мы исследуем класс графов, в которых окрестности вершин не содержат 3-лап и все $\mu$-подграфы являются регулярными графами валентности $\alpha$, где $\alpha >0$. В отличии от [30] мы не требуем даже равномощности всех $\mu$-подграфов. Поскольку наше условие на $\mu$-подграфы не влечет регулярности графа, то мы дополнительно накладываем на граф условие редуцированности.

ТЕОРЕМА 9.

Пусть $\Gamma$ -- связный граф, который удовлетворяет следующим условиям:

$(1)$ окрестность любой вершины из $\Gamma$ не содержит $3$-лап;

$(2)$ $\Gamma$ содержит $3$-лапу;

$(3)$ все $\mu$-подграфы из $\Gamma$ являются регулярными графами одинаковой валентности $\alpha$ для некоторого числа $\alpha >0$;

$(4)$ для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ состоит из единственной вершины $a$.

Тогда $\Gamma$ является локально $G$-графом, где $G$ один из следующих графов:

$(a)$ $\beta$-расширение решетчатого $m\times n$-графа при $\beta=\alpha /2$ и $m\geq 3$, $n\geq 3$;

$(b)$ треугольный граф $T(n)$ при $n\geq 6$;

$(c)$ граф Шлефли.

Если граф $G$ является $\beta$-расширением решетчатого $m\times n$-графа, то класс локально $G$-графов довольно широк и труден для изучения. Примерами таких графов являются графы Грассмана, графы Джонсона и их частные.

Пусть $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$.

Графы Джонсона и частные графов Джонсона дают нам примеры локально $n\times m$-графов. Эти примеры не исчерпывают класс таких графов. В статье [3] построены другие примеры локально $n\times m$-графов и найдены все локально $4\times 4$-графы. Там же получено описание локально $n\times m$-графов, в которых каждый $\mu$-подграф является объединением изолированных четырехугольников. Характеризация локально $n\times m$-графов при $n=3$ получена Дж. Холлом в [17]. Проблема полного описания локально $n\times m$-графов для любых $n, m$ остается открытой. Мало пока известно в общем случае и о локально треугольных графах.

Однако, если все $\mu$-подграфы из $\Gamma$ имеют диаметр 2, можно получить более точный ответ.

ТЕОРЕМА 10.

Пусть $\Gamma$ -- связный граф, который удовлетворяет условиям теоремы и все $\mu$-подграфы из $\Gamma$ имеют диаметр 2. Тогда $\Gamma$ является одним из следующих графов:

$(1)$ граф Грассмана;

$(2)$ граф Джонсона или его частное;

$(3)$ локально $T(n)$-граф при $n\geq 6$;

$(4)$ граф Госсета $E_7 (1)$.

Все графы Грассмана, графы Джонсона и их частные, граф Госсета $E_7 (1)$ являются дистанционно-транзитивными графами.

Заметим также, что граф системы корней $E_8$ (см. [5]) является локально $E_7 (1)$-графом и играет особую роль в теории графов, у которых любое собственное значение не меньше, чем $-2$. По теореме А.Дж. Хоффмана [23] любой такой граф является либо обобщенным реберным графом, либо подграфом $E_8 (1)$.

Заканчивается третья глава описанием сильно регулярных графов с расщепляемыми окрестностями вершин. Пусть $A,B,C$ -- некоторые множества. Скажем, что $A$ расщепляется $B$ и $C$, если $A$ содержится в $B\cup C$ и пересечение $A\cap B\cap C$ пусто. Э. Шульт в работе [33] классифицировал сильно регулярные графы, в которых для любого ребра $ab$ найдется такая вершина $c$ из $[a]$, что $[a]'$ расщепляется $[b]$ и $[c]$. Заметим, что в этом случае $[a]'\cap [b]=[a]'\cap [c]'$ и $[a]'\cap [c]=[a]'\cap [b]'$. В частности, антиокрестность $[a]'$ расщепляется антиокрестностями вершин $b$ и $c$. В следующей теореме [52] это условие накладывается на окрестности вершин, причем снято ограничение на расположение вершины $c$.

ТЕОРЕМА 11.

Пусть $\Gamma$ -- сильно регулярный граф, в котором для любого ребра $ab$ найдется такая вершина $c$, что $[a]$ расщепляется $[b]'$ и $[c]'$. Тогда граф $\Gamma$ изоморфен одному из следующих графов:

$(1)$ объединение $n$ полных подграфов при $n>1$;

$(2)$ решетчатый $n\times n$-граф при $n>1$;

$(3)$ пятиугольник;

$(4)$ сильно регулярный граф с параметрами $(13,6,2,3)$;

$(5)$ граф Шрикханде.

В последней главе диссертации изучаются некоторых теоретико-графовые свойства графов без 3-лап и их обобщений. В ней рассматривается, в частности, соотношение нижних параметров доминирования и неприводимости для графов без 3-лап и графов, все блоки которых не содержат 3-лап.

Некоторое множество $X$ вершин из графа $\Gamma$ называется доминирующим, если любая вершина, не принадлежащая $X$, смежна не менее чем с одной вершиной из $X$. Минимальное число элементов в доминирующем множестве вершин графа $\Gamma$ обозначается через $\gamma (\Gamma)$ и называется нижним параметром доминирования графа $\Gamma$. Множество всех вершин из графа $\Gamma$, смежных с вершиной $x$, вместе с $\{x\}$ называется замкнутой окрестностью вершины $x$. Вершина $x$ из $X$ неприводима относительно $X$ в $\Gamma$, если ее замкнутая окрестность содержит хотя бы одну вершину, не смежную ни с какой другой вершиной из $X$. Множество вершин $X$ называется неприводимым в $\Gamma$, если все его вершины неприводимы относительно $X$ в $\Gamma$. Заметим, что если $D$ -- минимальное доминирующее множество некоторого графа $\Gamma$, то оно неприводимо в $\Gamma$. Более того, множество $D$ является максимальным (относительно включения) неприводимым множеством графа $\Gamma$. Этот факт послужил основой для введения и изучения понятия неприводимости. Среди всех максимальных неприводимых множеств выберем множество $X$, содержащее наименьшее число вершин. Число вершин в $X$ назовем нижним параметром неприводимости для графа $\Gamma$ и обозначим через $ir(\Gamma)$.

Поскольку каждое минимальное доминирующее множество является максимальным неприводимым, то $ir(\Gamma)\le \gamma(\Gamma)$ для любого графа $\Gamma$. Неравенство $\gamma(\Gamma) < 2ir(\Gamma)$ было получено независимо в [1] и [4]. Изучению параметров доминирования и неприводимости в разных классах графов было посвящено несколько работ (см., например, [1], [4], [12], [16], [39]). В [12] П. Дамашке получил оценку $$\frac{\gamma (\Gamma)}{ir (\Gamma)}<\frac32$$ для случая, когда граф $\Gamma$ является деревом. Этот результат был расширен Л. Фолькманом в [39]. Он доказал неравенство $$\frac{\gamma (\Gamma)}{ir (\Gamma)}\leq \frac32$$ в случае, когда $\Gamma$ является блок-графом и в случае, когда граф $\Gamma$ содержит не более двух циклов.

Так как по определению любой блок в блок-графе является кликой, то точки сочленения внутри любого блока смежны между собой. Граф, обладающий таким свойством, назовем кликово-сочлененным графом.

В работе [41] показано, что оценка $$\frac{\gamma (\Gamma)}{ir (\Gamma)}\leq \frac32$$ справедлива для класса графов без 3-лап. Там же приводится серия примеров, которая показывает точность этой границы даже в классе раздуваний графов. Продолжая это исследование, мы изучаем нижние параметры доминирования и неприводимости в кликово-сочлененных графах, все блоки которых являются графами без 3-лап. В частности, покажем, что для них справедливо неравенство $$\frac{\gamma (\Gamma)}{ir(\Gamma)}\le \frac53$$. Более точно мы доказываем следующие два утверждения [48].

ТЕОРЕМА 12.

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

$(1)$ Если все блоки графа $\Gamma$ не содержат 3-лап, то существует доминирующее множество $D$ для $\Gamma$ такое, что выполнено неравенство $\vert D\vert/\vert X\vert\le 5/3$.

$(2)$ Если все блоки графа $\Gamma$ являются реберными графами графов без треугольников, то существует доминирующее множество $D$ для $\Gamma$ такое, что выполнено неравенство $\vert D\vert/\vert X\vert\le 3/2$.

Автор глубоко признателен профессору А.А. Махневу за дружеское участие, постоянное внимание и помощь в работе.