Reducing graphs by lifting rotations of edges to splittable graphs

Vitaly A. Baransky ; Valentin V. Zuev ; Tatiana A. Senchonok

Ural mathematical journal, Tome 10 (2024) no. 2, pp. 25-36

Résumé

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.

Détail

Keywords: Graphical partition, Degree partition, Splittable graph, Rotation of an edge
Mots-clés : Integer partition