Операция переключения ребер и расщепляемые предки графа

В. А. Баранский, Т. А. Сеньчонок

Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург

Аннотация: Пусть $r$ — ранг Дёрфи графа $G = (V, E)$, т. е. ранг Дёрфи его степенного разбиения $\mathrm{dpt}(G)$. Пусть $V_1$, $V_2$ — теоретико-множественное разбиение множества вершин $V$ на два непустых подмножества такое, что $\deg v\geq r$ для любого $v$ из $V_1$ и $\deg v \leq r$ для любого $v$ из $V_2$. Двудольный граф $(V_1, E', V_2)$ называется сэндвич подграфом графа $G$, отвечающим паре $V_1$, $V_2$, где $E'$ — множество всех ребер из $E$, которые идут из $V_1$ в $V_2$. Граф называется расщепляемым, если его множество вершин можно представить в виде объединения клики и коклики. Расщепляемый предок графа — это расщепляемый граф, который можно получить из $G$ с помощью некоторого последовательного выполнения повышающих вращений ребер. Расщепляемый предок графа $G$, имеющего ранг Дёрфи $r$, называется ближайшим расщепляемым $r$-предком графа $G$, если его можно получить из $G$ с помощью наименьшего возможного числа $s$ повышающих вращений ребер. Отметим, что $s = \frac{1}{2} (\mathrm{sum}\, \mathrm{tl}(\lambda) - \mathrm{sum}\, \mathrm{hd}(\lambda))$, где $\lambda = \mathrm{dpt}(G)$, $\mathrm{tl}(\lambda)$ — хвост и $\mathrm{hd}(\lambda)$ — голова разбиения $\lambda$. Цель работы состоит в доказательстве следующих двух утверждений. Пусть $r$ — ранг Дёрфи графа $G$, граф $G_1$ получен из графа $G$ с помощью процедуры переключения ребер, отвечающей некоторому чередующемуся $4$-циклу $C$. 1. Если $C$ не является чередующимся $4$-циклом сэндвич подграфа $(V_1, E, V_2)$ графа $G$, то графы $G$ и $G_1$ имеют общего ближайшего расщепляемого $r$-предка. 2. Если $C$ содержится в сэндвич подграфе $(V_1, E', V_2)$ графа $G$, то графы $G$ и $G_1$ имеют общего расщепляемого предка, который получается из каждого из них с помощью последовательности, состоящей не более чем из $s + 1$ повышающих вращений ребер.

Ключевые слова: целочисленное разбиение, графическое разбиение, степенное разбиение, расщепляемый граф, вращение ребра.

УДК: 519.176

MSC: 05C35, 05C07

Поступила в редакцию: 08.07.2025
Исправленный вариант: 07.09.2025
Принята в печать: 15.09.2025

DOI: 10.21538/0134-4889-2025-31-4-39-51

Реферативные базы данных:

•