|
Дискретный анализ и исследование операций, сер. 1, 2000, том 7, выпуск 2, страницы 12–20
(Mi da259)
|
|
|
|
Доминирование и неприводимость в графах с ограничениями на блоки
В. В. Кабанов Институт математики и механики УрО РАН
Аннотация:
Пусть $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.
Статья поступила: 30.11.1999
Образец цитирования:
В. В. Кабанов, “Доминирование и неприводимость в графах с ограничениями на блоки”, Дискретн. анализ и исслед. опер., сер. 1, 7:2 (2000), 12–20
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da259 https://www.mathnet.ru/rus/da/v7/s1/i2/p12
|
Статистика просмотров: |
Страница аннотации: | 389 | PDF полного текста: | 184 |
|