Аннотация

Тройка различных вершин графа такая, что и называется повышающей, если , и понижающей, если . Преобразование графа такое, что , называется вращением ребра в графе вокруг вершины , отвечающим тройке . Вращение ребра в графе , отвечающее тройке , называется повышающим, если тройка повышающая, и понижающим, если тройка понижающая. Вращение ребра в графе является повышающим тогда и только тогда, когда обратное к нему вращение ребра в графе является понижающим. Двудольный граф будем называть двудольно-пороговым графом, если он не имеет повышающих троек таких, что , или , . В работе найдены различные свойства, характеризующие двудольно-пороговые графы. В частности, каждый такой граф является подграфом порогового графа , где - полный граф на множестве вершин . Отметим, что граф является пороговым тогда и только тогда, когда он не имеет повышающих троек вершин. Любой двудольный граф может быть получен из двудольно-порогового графа с помощью понижающих вращений ребер. С помощью полученных результатов и критерия Кохнерта графичности разбиения мы приводим новое достаточно простое доказательство известной теоремы Гейла и Райзера о представлении двух разбиений степенными разбиениями долей двудольного графа.
Переведенное названиеBIPARTITE THRESHOLD GRAPHS
Язык оригиналаРусский
Страницы (с-по)56-67
Число страниц12
ЖурналТруды института математики и механики УрО РАН
Том26
Номер выпуска2
DOI
СостояниеОпубликовано - 2020

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

  • Applied Mathematics
  • Mathematics(all)
  • Computer Science Applications
  • Computational Mechanics

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

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

ГРНТИ

  • 27.00.00 МАТЕМАТИКА

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

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

Fingerprint Подробные сведения о темах исследования «ДВУДОЛЬНО-ПОРОГОВЫЕ ГРАФЫ». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать