EN|RU

Том 19, номер 4, 2012 г., Стр. 3-14

УДК 519.174.3
Алексеев В. Е., Мокеев В. Е. 
Кёниговы графы относительно 3-путей

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

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

Алексеев Владимир Евгеньевич 1
Мокеев Дмитрий Борисович 1,2

1. Нижегородский гос. университет,
пр. Гагарина, 23, корп. 2, 603950 Нижний Новгород, Россия
2. Национальный исслед. университет. Высшая школа экономики.
ул. Родионова, 136, 603093 Нижний Новгород, Россия
е-mail: aleve@rambler.ru, MokeevDB@gmail.com

Статья поступила 19 сентября 2011 г.
Исправленный вариант — 8 февраля 2012 г.

 © Институт математики им. С. Л. Соболева, 2015