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.