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