REDUCING GRAPHS BY LIFTING ROTATIONS OF EDGES TO SPLITTABLE GRAPHS

Abstract

A graph \(G\) is splittable if its set of vertices can be represented as the union of a clique and a coclique. We will call a graph \(H\) a splittable ancestor of a graph \(G\) if the graph \(G\) is reducible to the graph \(H\) using some sequential lifting rotations of edges and \(H\) is a splittable graph. A  splittable \(r\)-ancestor of \(G\) we will call its splittable ancestor whose Durfey rank is \(r\). Let us set \(s = ({1}/{2}) (\mathrm{sum}\,\mathrm{tl}(\lambda) - \mathrm{sum}\,\mathrm{hd}(\lambda))\), where \(\mathrm{hd}(\lambda)\) and \(\mathrm{tl}(\lambda)\) are the head and the tail of a partition \(\lambda\). The main goal of this work is to prove that any graph \(G\) of Durfey rank \(r\) is reducible by \(s\) successive lifting rotations of edges to a splittable \(r\)-ancestor \(H\) and \(s\) is the smallest non-negative integer with this property. Note that the degree partition \(\mathrm{dpt}(G)\) of the graph \(G\) can be obtained from the degree partition \(\mathrm{dpt}(H)\) of the splittable \(r\)-ancestor \(H\) using a sequence of \(s\) elementary transformations of the first type. The obtained results provide new opportunities for investigating the set of all realizations of a given graphical partition using splittable graphs.