TY - JOUR

T1 - ДВУДОЛЬНО-ПОРОГОВЫЕ ГРАФЫ

AU - Баранский, Виталий Анатольевич

AU - Сеньчонок, Татьяна Александровна

PY - 2020

Y1 - 2020

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

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

KW - Ferrer's diagram

KW - LATTICE

KW - PARTITIONS

KW - bipartite graph

KW - integer partition

KW - threshold graph

KW - Threshold graph

KW - Bipartite graph

KW - Integer partition

UR - https://elibrary.ru/item.asp?id=42950647

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000544885600004

UR - http://www.scopus.com/inward/record.url?scp=85090543773&partnerID=8YFLogxK

U2 - 10.21538/0134-4889-2020-26-2-56-67

DO - 10.21538/0134-4889-2020-26-2-56-67

M3 - Статья

VL - 26

SP - 56

EP - 67

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 2

ER -