Laboratory of Mathematical Logic at PDMI

Вторник, 19 сентября, комната 106. Начало в 12:00.

Докладчик: Д. В. Карпов.

ОСТОВНОЕ ДЕРЕВО С БОЛЬШИМ КОЛИЧЕСТВОМ ВИСЯЧИХ ВЕРШИН
В 1973 году B.Zelinka предложил алгоритм выделения в графе дерева с максимально возможным количеством висячих вершин. однако, до настоящего момента не опубликовано ни одной работы с оценкой на такое количество. Именно этому вопросу и будет посвящен доклад. будет доказано, что в связном графе, в котором никакие две вершины степени 2 не смежны, есть остовное дерево, в котором более 1/5 всех вершин висячие. будет доказана точность этой оценки.