An edge switching procedure and splittable ancestors of a graph

V. A. Baranskii, T. A. Senchonok

Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Abstract: Let $r$ be the Durfey rank of a graph $G = (V, E)$, i. e. the Durfey rank of its degree partition. Let $V_1$, $V_2$ be a set-theoretic partition of the vertex set $V$ into two nonempty subsets such that $\deg v \geq r$ for any $v \in V_1$ and $\deg v \geq r$ for any $v \in V_2$. The bipartite graph $(V_1, E', V_2)$ is called the sandwich subgraph of $G$ corresponding to the pair $V_1$, $V_2$, where $E'$ is the set of all edges in $E$ that go from $V_1$ to $V_2$. A graph $G$ is splittable graph 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 ancestor of a graph $G$ of Durfey rank $r$ is called nearest splittable $r$-ancestor of $G$ if it can be obtained from $G$ using the smallest possible number $s$ of lifting rotations of edges. Note that $s = \frac{1}{2} (\mathrm{sum}\, \mathrm{tl}(\lambda) - \mathrm{sum}\, \mathrm{hd}(\lambda))$, where $\lambda = \mathrm{dpt}(G)$, $\mathrm{tl}(\lambda)$ is the tail and $\mathrm{hd}(\lambda)$ is the head of the partition $\lambda$. The aim of this paper is to prove the following two statements. Let $r$ be the Durfey rank of a graph $G$, and let $G_1$ be a graph obtained from $G$ using an edge switching procedure corresponding to some alternating 4-cycle $C$. 1. If $C$ is not an alternating 4-cycle of the sandwich subgraph $(V_1, E', V_2)$ of $G$, then $G$ and $G_1$ have a common nearest splittable $r$-ancestor. 2. If $C$ is contained in a sandwich subgraph $(V_1, E', V_2)$ of $G$, then $G$ and $G_1$ have a common splittable ancestor that is obtained from each of them by a sequence of at most $s + 1$ lifting rotations of edges.

Keywords: integer partition, graphical partition, degree partition, splittable graph, rotation of an edge.

UDC: 519.176

MSC: 05C35, 05C07

Received: 08.07.2025
Revised: 07.09.2025
Accepted: 15.09.2025

DOI: 10.21538/0134-4889-2025-31-4-39-51

Bibliographic databases:

•