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

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

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

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

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

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

Литература

[1] Ding G., Xu Z., ZangW. Packing cycles in graphs. II // J. Comb. Theory. Ser. B. — 2003. — Vol. 87. — P. 244–253.

[2] Grõtschel M., Lovász L., Schrijver A. Geometric algorithms and combinatorial optimization. — Berlin; Heidelberg: Springer-Verl., 1993. — 362 p.

[3] Hell P. Graph packing // Electron. Notes Discrete Math. — 2000. — Vol. 5. — P. 170–173.

[4] Yuster R. Combinatorial and computational aspects of graph packing and graph decomposition // Comput. Sci. Rev. — 2007. — Vol. 1. — P. 12–26.