Статья: 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)(sumtl(λ)−sumhd(λ)), where hd(λ) and tl(λ) are the head and the tail of a partition λ. 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 dpt(G) of the graph G can be obtained from the degree partition 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.