DOI

Тройка вершин  в графе  такая, что  и , называется повышающей, если  и - понижающей, если . Понижающим вращением ребра в графе , отвечающим понижающей тройке , называется преобразование графа, при котором ребро  заменяется на ребро . В работе доказано, что граф является пороговым тогда и только тогда, когда он не содержит повышающих троек вершин. Из этого результата вытекают три следствия. Графическое разбиение, отвечающее графу , является максимальным графическим разбиением тогда и только тогда, когда граф  является пороговым. Произвольное разбиение  является максимальным графическим разбиением тогда и только тогда, когда голова разбиения  равна его хвосту. Для произвольного графического разбиения  все его реализации  получаются с помощью конечных последовательностей понижающих вращений ребер из пороговых реализаций  подходящих максимальных графических разбиений  таких, что .

Переведенное названиеOn threshold graphs and realizations of graphical partitions
Язык оригиналаРусский
Страницы (с-по)22-31
Число страниц10
ЖурналТруды института математики и механики УрО РАН
Том23
Номер выпуска2
DOI
СостояниеОпубликовано - 2017

    ГРНТИ

  • 27.45.00 Комбинаторный анализ. Теория графов

    Предметные области WoS

  • Математика, Прикладная

    Уровень публикации

  • Перечень ВАК

ID: 8559466