Результаты исследований: Вклад в журнал › Статья › Рецензирование
Тройка вершин в графе такая, что и , называется повышающей, если и - понижающей, если . Понижающим вращением ребра в графе , отвечающим понижающей тройке , называется преобразование графа, при котором ребро заменяется на ребро . В работе доказано, что граф является пороговым тогда и только тогда, когда он не содержит повышающих троек вершин. Из этого результата вытекают три следствия. Графическое разбиение, отвечающее графу , является максимальным графическим разбиением тогда и только тогда, когда граф является пороговым. Произвольное разбиение является максимальным графическим разбиением тогда и только тогда, когда голова разбиения равна его хвосту. Для произвольного графического разбиения все его реализации получаются с помощью конечных последовательностей понижающих вращений ребер из пороговых реализаций подходящих максимальных графических разбиений таких, что .
Переведенное название | On threshold graphs and realizations of graphical partitions |
---|---|
Язык оригинала | Русский |
Страницы (с-по) | 22-31 |
Число страниц | 10 |
Журнал | Труды института математики и механики УрО РАН |
Том | 23 |
Номер выпуска | 2 |
DOI | |
Состояние | Опубликовано - 2017 |
ID: 8559466