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

Дискретн. анализ и исслед. опер., 2019, том 26, выпуск 1, страницы 74–88 (Mi da918)

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

Кёниговы графы относительно 4-пути и его остовных надграфов

Д. С. Малышевa, Д. Б. Мокеевba

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

Аннотация: Описывается класс графов, у которых для каждого подграфа максимальное число вершинно непересекающихся 4-путей равно минимальной мощности множества вершин таких, что каждый 4-путь подграфа содержит хотя бы одну из этих вершин. Полностью описано множество минимальных запрещённых подграфов данного класса. Кроме того, представлено альтернативное описание класса, в основе которого лежит операция подразбиения рёбер, применяемая к двудольным мультиграфам, и добавление так называемых висячих подграфов, изоморфных треугольникам и звёздам. Ил. 1, библиогр. 19.

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

УДК: 519.174.3

Статья поступила: 12.12.2017
Переработанный вариант: 30.10.2018
Принята к публикации: 28.11.2018

DOI: 10.33048/daio.2019.26.606


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2019, 13:1, 85–92

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


© МИАН, 2024