Laboratory of Mathematical Logic at PDMI

Пятница, 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.