Home

Пятница 23 мая, 15-00, ауд. 203

Пятница, 23 мая, ауд. 203. Начало в 15:00.

Докладчик: А.В. Пастор (ПОМИ РАН).

Тема: О вершинах степени 6 в $ C_3 $-критических минимальных 6-связных графах.

Abstract

Понятие $ C_m $-критического $ k $-связного графа ввел в 1988 году W.Mader. Это понятие является естественным обобщением понятий критического и минимального по стягиванию (contraction-critical) $ k $-связного графа: $ k $-связный граф называется $ C_m $-критическим, если любая его клика, содержащая не более $ m $ вершин, содержится в некотором $ k $-разделяющем множестве. В связи с этим, интересно перенести на случай $ C_m $-критических $ k $-связных графов задачи, ранее изучавшиеся для случая минимальных по стягиванию графов.

Вопросы о количестве вершин степени $ k $ в минимальных или минимальных по стягиванию $ k $-связных графах исследовались в работах многих авторов и стали уже классическими. Однако исследования вершин степени $ k $ в $ C_m $-критических $ k $-связных графах при $ m>2 $, насколько мне известно, ранее не проводились. В моем докладе я сделаю краткий обзор известных результатов в этой области и докажу, что в $ C_3 $-критическом минимальном 6-связном графе не менее 5/9 его вершин имеют степень 6.