Abstract:
A triple of 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)\geq2+\mathrm{deg}(y)$. A lowering rotation of an edge in a graph $G$ corresponding to a lowering triple $(x,v,y)$ is a transformation of this graph that replaces the edge $xv$ by the edge $vy$. We prove that $G$ is a threshold graph if and only if it has no lifting triples of vertices. This result has three corollaries: The graphical partition corresponding to $G$ is a maximal graphical partition if and only if $G$ is a threshold graph. An arbitrary partition $\lambda$ is a maximal graphical partition if and only if the head of $\lambda$ is equal to its tail. Each realization of an arbitrary graphical partition $\mu$ can be obtained by a finite sequence of lowering rotations of edges from a threshold realization of an appropriate maximal graphical partition $\lambda$ such that $\lambda\geq\mu$.