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
REFERENCES
1. Asanov M.O., Baransky V.A., Rasin V.V. Diskretnaya matematika: grafy, matroidy, algoritmy [Discrete Mathematics: graphs, matroids, algorithms]. SPb: Lan’ Publ., 2010. 368 p.
2. Andrews G.E. The theory of partitions. Cambridge: Cambridge Univ. Press, 1976. 255 p.
3. Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Ser. Annals of Discr. Math., vol. 56, Amsterdam: North-Holland Publ. Co., 1995, 542 p.
4. Baransky V.A., Koroleva T.A., Senchonok T.A. On the partition lattice of all integers . Sib. Elektron. Mat. Izv., 2016, vol. 13, pp. 744–753 (in Rissian). doi: 10.17377/semi.2016.13.060
5. Baransky V.A., Senchonok T.A. On the shortest sequences of elementary transformations in the partition lattice. Sib. Elektron. Mat. Izv., 2018, vol. 15, pp. 844–752 (in Rissian). 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, pp. 477–481.
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.
