Laboratory of Mathematical Logic at PDMI

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

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

ОЦЕНКИ СНИЗУ НА МАКСИМАЛЬНОЕ КОЛИЧЕСТВО ВИСЯЧИХ ВЕРШИН В ОСТОВНОМ ДЕРЕВЕ ГРАФА
Будет доказано, что в любом связном графе, степени вершин которого не менее 3, можно выделить остовное дерево, в котором более 1/4 всех вершин висячие, а в любом связном графе, степени вершин которого не менее 4, можно выделить остовное дерево, в котором более 2/5 всех вершин висячие. будут приведены бесконечные серии примеров, показывающие оптимальность этих оценок.
Для связного графа, степени всех вершин которого не менее d (d>4) будет приведен алгоритм выделения остовного дерева с большим количеством висячих вершин, будут доказаны оценки снизу на количество висячих вершин в остовном дереве такого графа.