REDUCING GRAPHS BY LIFTING ROTATIONS OF EDGES TO SPLITTABLE GRAPHS

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.

Abstract licence: CC BY-NC-SA

7 more references, whose wording the paper’s licence keeps private.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.