Том 7, серия 1, номер 2, 2000 г., Стр. 12-20

УДК 519.14
В. В. Кабанов
Доминирование и неприводимость в графах с ограничениями на блоки

Аннотация:
Пусть $G=(V,E)$ – неориентированный граф без петель и кратных ребер с множеством вершин $V$ и множеством ребер $E$, $N(v)$ – множество всех вершин в $G$, смежных с вершиной $v$, и $N[v]=N(v)\cup\{v\}$. Множество $PN(v)=N[v]\setminus N[X\setminus\{v\}]$, где $v$ – вершина из подмножества $X\subseteq V$, называется $X$-приватной окрестностью вершины $v$ в $G$, а его элементы – $X$-приватными соседями для $v$. Вершина $v$ из $X$ неприводима относительно $X$, если ее $X$-приватная окрестность не является пустым множеством. В противном случае $v$ называется приводимой относительно $X$. Множество вершин $X$ называется неприводимым в $G$, если все его вершины неприводимы относительно $X$ в $G$. Наименьшее число вершин в максимальном неприводимом множестве графа $G$ называется нижним параметром неприводимости для графа $G$ и обозначается через $\operatorname ir(G)$. Минимальное число элементов в доминирующем множестве вершин графа $G$ обозначается через $\gamma(G)$ и называется нижним параметром доминирования графа $G$. В статье изучается соотношение нижних параметров доминирования и неприводимости графов, в которых все блоки не содержат порожденных $K_{1,3}$ подграфов и точки сочленения каждого блока образуют клику. Полученные результаты обобщают и расширяют результаты Л. Фолькмана о блок-графах и графах с числом циклов не более 2.
Ил. 1, библиогр. 7.

Кабанов В. В. ¹
1. Институт математики и механики УрО РАН,
ул. Ковалевской, 16, 620219 Екатеринбург, Россия
е-mail: vvk@imm.uran.ru

Статья поступила 30 ноября 1999 г.