An algorithm for taking a bipartite graph to the bipartite threshold form

V. A. Baranskii ; T. A. Senchonok

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 4, pp. 54-63

Résumé

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.

Détail

Keywords: algorithm, threshold graph, bipartite threshold graph, Ferrers diagram.
Mots-clés : integer partition, bipartite graph

Bibliographie

[1] Asanov M.O., Baranskii V.A., Rasin V.V., Diskretnaya matematika: grafy, matroidy, algoritmy, 2-e izd., ispr. i dop., Lan, SPb., 2010, 368 pp.

[2] Andrews G.E., The theory of partitions, Cambridge Univ. Press, Cambridge, 1976, 255 pp. | MR

[3] Ivanyi A., Lucz L., Gombos G., Matuszka T., “Parallel enumeration of degree sequences of simple graphs”, Acta Univ. Sapientiae, Informatica, 4:2 (2012), 260–288

[4] Baranskii V.A., Senchonok T.A., “Dvudolno-porogovye grafy”, Tr. In-ta matematiki i mekhaniki UrO RAN, 26:2 (2020), 56–67 | DOI | MR

[5] Mahadev N.V.R., Peled U.N., Threshold graphs and related topics, Ser. Annals of Discr. Math., 56, North-Holland Publishing Co, Amsterdam, 1995, 542 pp. | MR

[6] Baransky V.A., Senchonok T.A., “On maximal graphical partitions that a the nearest to a given graphical partition”, Sib. Elect. Math. Reports, 17 (2020), 338–363 | DOI | MR