Laboratory of Mathematical Logic

Пятница, 7 мая, комната 106. Начало в 14:00.

Докладчик: Е. В. Просолупов.

Тема: Дублирование вершин и функции интервала

.

Abstract

Доклад по диссертации Просолупова Е.В.

Определим операцию дублирования вершин графа как добавление к каждой вершине графа

новой вершины, смежной в новом графе с теми и только с теми вершинами, с которыми была смежна исходная вершина в

. В рамках данной работы рассмотрим свойства графом получаемых с помощью данной операции. Изучим класс графов, в построении которого участвует описанная операция, который обладает тем свойством, что для любого натурального числа

в этом классе можно выделить такую последовательность графов

, что любой граф

с

и заданным числом вершин будет подграфом всех членов последовательности, начиная с некоторого номера.

Также рассмотрим свойства нескольких функций, значения которых попадают в интервал между размером максимального независимого множества (

) и минимальным количеством клик, которыми можно покрыть все вершины графа (

).