Home

Семинар 7 мая 2004 года

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

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

Тема: Дублирование вершин и функции интервала $ [alpha(G),overlinechi(G)] $.

Abstract

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

Определим операцию дублирования вершин графа как добавление к каждой вершине графа $ G $ новой вершины, смежной в новом графе с теми и только с теми вершинами, с которыми была смежна исходная вершина в $ G $. В рамках данной работы рассмотрим свойства графом получаемых с помощью данной операции. Изучим класс графов, в построении которого участвует описанная операция, который обладает тем свойством, что для любого натурального числа $ t $ в этом классе можно выделить такую последовательность графов $ {F^{(t)}_i} $, что любой граф $ G $ с $ chi(G)leq t $ и заданным числом вершин будет подграфом всех членов последовательности, начиная с некоторого номера.

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