В. Е. Алексеев, Д. Б. Мокеев, “Кёниговы графы относительно $3$-путей”, Дискретн. анализ и исслед. опер., 2012, том 19, выпуск 4,страницы 3

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

Кёниговы графы относительно $3$-путей

В. Е. Алексеев^a, Д. Б. Мокеев^ab

^a Нижегородский гос. университет, Нижний Новгород, Россия
^b Национальный исслед. университет «Высшая школа экономики», Нижний Новгород, Россия

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

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

УДК: 519.174.3

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