V.A. Baranskii, T.A. Sen’chonok. An algorithm for taking a bipartite graph to the bipartite threshold form ... P. 54-63

A triple of different vertices $(x,v,y)$ of 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 $\phi$ of the graph $G$ that replaces $G$ with $\phi(G) = G - xv + vy$ is called an edge rotation in the graph $G$ about the vertex $v$ corresponding to the 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 is lowering in the graph $\phi(G)$. 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 edge rotation corresponding to a triple of vertices $(x, v, y)$ such that $x,y \in V_1$ and $v \in V_2$ ($x,y \in V_2$ and $v \in V_1$) is called a $V_1$-rotation ($V_2$-rotation) of edges. Every bipartite graph $H = (V_1, E, V_2)$ can be transformed to a bipartite threshold graph by a finite sequence of $V_1$-rotations ($V_2$-rotations) of edges. The aim of the paper is to give a polynomial algorithm that transforms every bipartite graph $H=(V_1,E,V_2)$ to a bipartite threshold graph by a shortest finite sequence of $V_1$-rotations of edges.

Keywords: algorithm, integer partition, threshold graph, bipartite graph, bipartite threshold graph, Ferrers diagram

Received August 15, 2022

Revised September 15, 2022

Accepted September 26, 2022

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. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 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. ISBN: 978-5-8114-1068-2 .

2.   Andrews G.E. The theory of partitions. Cambridge: Cambridge University Press, 1984, 255 p. doi: 10.1017/CBO9780511608650 

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

4.   V. A. Baransky, T. A. Senchonok. Bipartite threshold graphs. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 2, pp. 56-67 (in Russian). doi: 10.21538/0134-4889-2020-26-2-56-67 

5.   Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Ser. Annals of Discr. Math., vol. 56. Amsterdam: North-Holland, 1995, 542 p. doi: 10.1016/s0167-5060(13)71063-x 

6.   Baransky V.A., Senchonok T.A. On maximal graphical partitions that are the nearest to a given graphical partition. Sib. Elektron. Mat. Izv., 2020, vol. 17, pp. 338–363 (in Russian). doi: 10.33048/semi.2020.17.022 

Cite this article as: V.A. Baranskii, T.A. Sen’chonok. An algorithm for taking a bipartite graph to the bipartite threshold form. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 4, pp. 54–63