В.А. Баранский, Т.А. Сеньчонок. Двудольно-пороговые графы ... С. 56-67

УДК 519.176

MSC: 05C35

DOI: 10.21538/0134-4889-2020-26-2-56-67

Тройка $(x, v, y)$ различных вершин графа $G = (V, E)$ такая, что $xv\in E$ и $vy\notin E$ называется повышающей, если $\mathrm{deg}(x)\leq \mathrm{deg}(y)$, и понижающей, если $\mathrm{deg}(x)\geq 2 + \mathrm{deg}(y)$.  Преобразование $\varphi$ графа $G$ такое, что $\varphi(G) = G - xv + vy$, называется вращением ребра в графе $G$ вокруг вершины $v$, отвечающим тройке $(x, v, y)$. Вращение ребра в графе $G$, отвечающее тройке $(x, v, y)$, называется повышающим, если тройка $(x, v, y)$ повышающая, и понижающим, если тройка $(x, v, y)$ понижающая. Вращение $\varphi$ ребра в графе $G$ является повышающим тогда и только тогда, когда обратное к нему вращение ребра в графе $\varphi(G)$ является понижающим. Двудольный граф $H = (V_1, E, V_2)$ будем называть двудольно-пороговым графом, если он не имеет повышающих троек таких, что $x, y \in V_1$, $v \in V_2$ или $x, y \in V_2$, $v \in V_1$. В работе найдены различные свойства, характеризующие двудольно-пороговые графы. В частности, каждый такой граф $(V_1, E, V_2)$  является подграфом порогового графа $(K(V_1),  E, V_2)$, где $K(V_1)$ - полный граф на множестве вершин $V_1$. Отметим, что граф является пороговым тогда и только тогда, когда он не имеет повышающих троек вершин. Любой двудольный граф может быть получен из двудольно-порогового графа с помощью понижающих вращений ребер. С помощью полученных результатов и критерия Кохнерта графичности разбиения мы приводим новое достаточно простое доказательство известной теоремы Гейла и Райзера о представлении двух разбиений степенными разбиениями долей двудольного графа.

Ключевые слова: разбиение, пороговый граф, двудольный граф, диаграмма Ферре

СПИСОК ЛИТЕРАТУРЫ

1.   Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. 2-е изд., испр. и доп. СПб.: Лань, 2010. 368 c.

2.   Andrews G.E. The theory of partitions. Cambridge: Cambridge University Press, 1976. 255 p.

3.   Ivanyi A., Lucz L., Gombos G., Matuszka T. Parallel enumeration of degree sequences of simple graphs // Acta Univ. Sapientiae, Informatica. 2012. Vol. 4, № 2. P. 260–288.

4.   Tripathi A., Venugopalan S., West D.B. A short constructive proof of the Erdos–Gallai characterization of graphic lists // Discrete Math. 2010. Vol. 310, № 4. P. 833–834. doi: 10.1016/j.disc.2009.09.023 

5.   Bisi C., Ciaselotti G., Oliverio P.A. A natural extension of the Young partition lattice // Advances in Geometry. 2015. Vol. 15, № 3. P. 263–280. doi: 10.1515/advgeom-2015-0017 

6.   Baransky V.A., Koroleva T.A. The lattice of partitions of a positive integer // Dokl. Math. 2008. Vol. 77, № 1. P. 72–75.

7.   Baransky V.A., Koroleva T.A., Senchonok T.A. On the partition lattice of all integers // Sib. Elect. Math. Reports. 2016. Vol. 13. P. 744–753. doi: 10.17377/semi.2016.13.060 

8.   Kohnert A. Dominance order and graphical partitions // Elec. J. Comb. 2004. Vol. 11, № 4. P. 1–17. doi: 10.37236/1845 

9.   Erdos P., Gallai T. Graphs with given degree of vertices // Math. Lapok. 1960. Vol. 11. P. 264–274.

10.   Baransky V.A., Senchonok T.A. On maximal graphical partitions that a the nearest to a given graphical partition // Sib. Elect. Math. Reports. 2020. Vol. 17. P. 338–363. doi: 10.33048/semi.2020.17.022 

11.   Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Amsterdam: North-Holland Publishing Co., 1995. Vol. 56. 542 p. (Ser. Annals of Discr. Math.)

12.   Baransky V.A., Senchonok T.A. On the shortest sequences of elementary transformations in the partition lattice // Sib. Elect. Math. Reports. 2018. Vol. 15. P. 844–852. doi: 10.17377/semi.2018.15.072 

Поступила 15.03.2020

После доработки 8.05.2020

Принята к публикации 18.05.2020

Баранский Виталий Анатольевич
д-р физ.-мат. наук, профессор
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: vitaly.baransky@urfu.ru

Сеньчонок Татьяна Александровна
канд. физ.-мат. наук
доцент
Уральский федеральный университет
г. Екатеринбург
e-mail: tatiana.senchonok@urfu.ru

Ссылка на статью: В.А. Баранский, Т.А. Сеньчонок. Двудольно-пороговые графы // Тр. Ин-та математики и механики УрО РАН. 2020. Т.26, № 2. С. 56-67 

English

V.A. Baransky, T.A. Senchonok. Bipartite threshold graphs

A triple of distinct  vertices $(x,v,y)$ in a graph $G=(V,E)$ such that $xv\in E$ and $vy\notin E$ is called lifting if $\mathrm{deg}(x)\leq \mathrm{deg}(y)$ and lowering if $\mathrm{deg}(x)\geq 2+\mathrm{deg}(y)$. A transformation $\varphi$ of a graph $G$ that replaces $G$ with $\varphi(G)=G-xv+vy$ is called an edge rotation corresponding to a triple of vertices $(x,v,y)$. For a lifting (lowering) triple $(x,v,y)$, the corresponding edge rotation is called lifting (lowering). An edge rotation in a graph $G$ is lifting if and only if its inverse in the graph $\varphi(G)$ is lowering. A bipartite graph $H=(V_1,E,V_2)$ is called a  bipartite threshold graph if it has no lifting triples such that $x,y\in V_1$ and $v\in V_2$ or $x, y\in V_2$ and $v\in V_1$. The aim of paper is to give some characteristic properties of bipartite threshold graphs. In particular, every such graph $(V_1,E,V_2)$ is embedded in the threshold graph $(K(V_1),E,V_2)$, where $K(V_1)$ is the complete graph on the vertex set $V_1$. Note that a graph is a threshold graph if and only if it has no lifting triples of vertices. Every bipartite graph can be obtained from a bipartite threshold graph by means of lowering edge rotations. Using the obtained results and Kohnert's criterion for a partition to be graphical, we give a new simple proof of the well-known Gale-Ryser theorem on the representation of two partitions by degree partitions of the parts in a bipartite graph.

Keywords: integer partition, threshold graph, bipartite graph, Ferrer's diagram

Received March 15, 2019

Revised May 8, 2020

Accepted May 18, 2020

Vitaly Anatol’evich Baransky, Dr. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: vitaly.baransky@urfu.ru

Tatiana Aleksandrovna Senchonok, Cand. Phys.-Math. Sci., Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: tatiana.senchonok@urfu.ru

Cite this article as: V.A.Baransky, T.A.Senchonok. Bipartite threshold graphs. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 2, pp. 56-67.

[References -> on the "English" button bottom right]