Search
Семинар 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)$).