Известия Саратовского университета. Новая серия.
ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Т-неприводимое расширение

Т-неприводимое расширение для объединения цепей и циклов

Расширением n-вершинного графа G называется граф H с n+1 вершинами такой, что граф G вкладывается в каждый максимальный подграф графа H. Тривиальное расширение графа G – соединение графа G с одноэлементным графом (т.е. к графу G добавляется вершина, которая соединяется ребром с каждой вершиной графа G).

Т-неприводимые расширения для сверхстройных деревьев

Рассматривается один из способов построения оптимального расширения графа — Т-неприводимое расширение (ТНР). До сих пор остается нерешенной следующая задача: построить одно из ТНР для произвольного сверхстройного дерева. Данная задача была решена С. Г. Курносовой для подкласса сверхстройных деревьев –- пальм. Для несложных сверхстройных деревьев данная задача была решена М. Б. Абросимовым.