Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретный анализ и исследование операций, сер. 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
Реферативные базы данных:
УДК: 519.14
Образец цитирования: В. В. Кабанов, “Доминирование и неприводимость в графах с ограничениями на блоки”, Дискретн. анализ и исслед. опер., сер. 1, 7:2 (2000), 12–20
Цитирование в формате AMSBIB
\RBibitem{Kab00}
\by В.~В.~Кабанов
\paper Доминирование и~неприводимость в~графах с~ограничениями на блоки
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2000
\vol 7
\issue 2
\pages 12--20
\mathnet{http://mi.mathnet.ru/da259}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1758477}
\zmath{https://zbmath.org/?q=an:0963.05100}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da259
  • https://www.mathnet.ru/rus/da/v7/s1/i2/p12
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:389
    PDF полного текста:184
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024