RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2017, том 24, выпуск 3, страницы 61–79 (Mi da875)

Эта публикация цитируется в 4 статьях

О кёниговых графах относительно $P_4$

Д. Б. Мокеевab

a Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950 Нижний Новгород, Россия
b НИУ Высшая школа экономики в Нижнем Новгороде, ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия

Аннотация: Описывается класс графов, у которых для каждого порождённого подграфа максимальное число непересекающихся порождённых путей с четырьмя вершинами равно минимальной мощности множества вершин таких, что каждый такой путь содержит хотя бы одну из них. В основе описания лежит операция замены вершин кографами, применяемая к вершинам графов, полученных из двудольных графов подразбиением их цикловых рёбер. Библиогр. 13.

Ключевые слова: упаковка подграфов, вершинное покрытие подграфов, четырёхвершинный путь, кёнигов граф.

УДК: 519.174.3

Статья поступила: 30.12.2016
Переработанный вариант: 24.01.2017

DOI: 10.17377/daio.2017.24.561


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2017, 11:3, 421–430

Реферативные базы данных:


© МИАН, 2024