УДК 519.176
MSC: 05A17
DOI: 10.21538/0134-4889-2023-29-1-24-35
Полный текст статьи (Full text)
Двудольный граф $H = (V_1, E, V_2)$ будем называть двудольно-пороговым графом, если он не имеет повышающих троек $(x,v,y)$ таких, что $x, y \in V_1$, $v \in V_2$ или $x, y \in V_2$, $v \in V_1$. Любой двудольный граф $H = (V_1, E, V_2)$ можно преобразовать в двудольно-пороговый граф с помощью конечной последовательности таких двудольных повышающих вращений ребер. В нашей предыдущей работе мы изучили свойства двудольно-пороговых графов и отметили их важность для класса пороговых графов. Теперь мы хотим показать важность этих графов для класса двудольных графов. Под разбиением мы всегда будем понимать невозрастающую последовательность целых неотрицательных чисел, которая содержит лишь конечное число ненулевых компонент. Для любых разбиений $\alpha$ и $\beta$ таких, что $\mathrm{sum}(\alpha) = \mathrm{sum}(\beta)$ и $\alpha\leq\beta^*$, где $\beta^*$ — сопряженное к $\beta$ разбиение, через $\mathrm{BG}(\alpha, \beta)$ будем обозначать семейство двудольных графов $H = (V_1, E, V_2)$, реализующих пару разбиений $(\alpha, \beta)$, т. е. всех таких двудольных графов, что исходная пара разбиений составлена из степеней вершин соответственно первой и второй долей этого графа, дополненных нулями. В данной работе мы даем описание двудольно-пороговых графов, составляющих семейство $\mathrm{BTG}_\uparrow(\alpha, \beta)$, всех двудольно-пороговых графов, которые можно получить из графов семейства $\mathrm{BG}(\alpha, \beta)$ с помощью двудольных повышающих вращений ребер. Также находим наименьшую длину последовательностей двудольных повышающих вращений ребер, переводящих графы из $\mathrm{BG}(\alpha, \beta)$ в графы из $\mathrm{BTG}_\uparrow(\alpha, \beta)$, даем алгоритм, который находит двудольно-пороговый граф, принадлежащий семейству $\mathrm{BG}(\alpha, \beta)$, и получаем описание процедуры, которая позволяет из одного графа семейства $\mathrm{BG}(\alpha, \beta)$ получить все графы этого семейства.
Ключевые слова: разбиение, пороговый граф, двудольный граф, двудольно-пороговый граф, диаграмма Ферре
СПИСОК ЛИТЕРАТУРЫ
1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. 2-е изд., испр. и доп. СПб.: Лань, 2010. 368 c.
2. Andrews G.E. The theory of partitions. Cambridge: Cambridge University Press, 1976. 255 p.
3. Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Amsterdam: North-Holland Publishing Co., 1995. 542 p. (Ser. Annals of Discr. Math.; vol. 56.)
4. Баранский В.А., Королева Т.А., Сеньчонок Т.А. О решетке разбиений всех натуральных чисел // Сиб. электрон. мат. изв. 2016. Т. 13. С. 744–753. doi: 10.17377/semi.2016.13.060
5. Баранский В.А., Сеньчонок Т.А. О кратчайших последовательностях элементарных преобразований в решетке разбиений натуральных чисел // Сиб. электрон. мат. изв. 2018. Т. 15. С. 844–852. doi: 10.17377/semi.2018.15.072
6. Havel V. A remark on the existence of finite graphs (in Czech) // Cǎsopic Pěst. Mat. 1955. Vol. 80, no. 4. P. 477–481.
Поступила 7.11.2022
После доработки 3.02.2023
Принята к публикации 6.02.2023
Баранский Виталий Анатольевич
д-р физ.-мат. наук, профессор
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: vitaly.baransky@urfu.ru
Сеньчонок Татьяна Александровна
канд. физ.-мат. наук
доцент
Уральский федеральный университет
г. Екатеринбург
e-mail: tatiana.senchonok@urfu.ru
Ссылка на статью: В.А. Баранский, Т.А. Сеньчонок. Двудольно-пороговые графы и повышающие вращения ребер в двудольных графах // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 24-35
English
V.A. Baranskii, T.A. Sen’chonok. Bipartite-threshold graphs and lifting rotations of edges in bipartite graphs
A bipartite graph $H=(V_1,E,V_2)$ is called a bipartite-threshold graph if it has no lifting triples $(x,v,y)$ such that $x,y\in V_1$, $v\in V_2$ or $x,y\in V_2$, $v\in V_1$. Every bipartite graph $H=(V_1,E,V_2)$ can be transformed to a bipartite-threshold graph by a finite sequence of such bipartite lifting rotations of edges. In our previous paper, we studied the properties of bipartite-threshold graphs and noted their importance for the class of threshold graphs. Now we want to show the importance of these graphs for the class of bipartite graphs. We will always understand an integer partition as a nonincreasing sequence of nonnegative integers that contains only finitely many nonzero terms. For any integer partitions $\alpha$ and $\beta$ such that $\mathrm{sum}(\alpha)=\mathrm{sum}(\beta)$ and $\alpha\leq\beta^*$, where $\beta^*$ is the conjugate partition of $\beta$, we denote by $\mathrm{BG}(\alpha, \beta)$ the family of bipartite graphs $H=(V_1,E,V_2)$ implementing the pair of partitions $(\alpha, \beta)$, i.e., the family of all bipartite graphs for which the given pair of partitions is composed of the degrees of vertices in the first and second parts of the graph, respectively, supplemented with zeros. In this paper we describe the bipartite-threshold graphs from the family $\mathrm{BTG}_\uparrow(\alpha, \beta)$ of all bipartite-threshold graphs that can be obtained from the graphs of the family $\mathrm{BG}(\alpha, \beta)$ by bipartite lifting rotations of edges. We also find the smallest length of sequences of bipartite lifting rotations of edges transforming graphs from $\mathrm{BG}(\alpha,\beta)$ to graphs belonging to $\mathrm{BTG}_\uparrow(\alpha, \beta)$, give an algorithm that finds a bipartite-threshold graph from $\mathrm{BG}(\alpha, \beta)$, and describe a procedure that generates all graphs in a family $\mathrm{BG}(\alpha, \beta)$ from one graph of this family.
Keywords: integer partition, threshold graph, bipartite graph, bipartite-threshold graph, Ferrers diagram
Received November 7, 2022
Revised February 3, 2023
Accepted February 6, 2023
Vitaly Anatol’evich Baransky, Dr. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: vitaly.baransky@urfu.ru
Tatiana Aleksandrovna Senchonok, Cand. Sci. (Phys.-Math.), Ural Federal University, 620000 Russia, e-mail: tatiana.senchonok@urfu.ru
Cite this article as: V.A. Baranskii, T.A. Sen’chonok. Bipartite-threshold graphs and lifting rotations of edges in bipartite graphs. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 1, pp. 24–35.
[References -> on the "English" button bottom right]
