Home

Пятница, 28 мая, 18:00, к. 106

Пятница, 28 мая, ауд. 106. Начало в 18:00.

Докладчик: Д. В. Карпов (ПОМИ РАН).

Тема: Остовные деревья в графах без цепочек вершин степени 2.

Abstract

Для связного графа $ G(V,E) $, в котором никакие две вершины степени 2 не смежны, доказывается существование остовного дерева, в котором более чем $ |V|\over 6 $ вершин являются висячими. Доказательство содержит описание полиномиального алгоритма построения такого остовного дерева. Доказывается, что константу $ {1\over6} $ нельзя заменить на большую.