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
Received July 8, 2025
Revised September 7, 2025
Accepted September 15, 2025
Vitaly Anatol’evich Baransky, Dr. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: vitaly.baransky@urfu.ru
Tatiana Aleksandrovna Senchonok, Cand. Sci. (Phys.-Math.), Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: tatiana.senchonok@urfu.ru
REFERENCES
1. Baransky V.A., Senchonok T.A. Around the ErdЈos — Gallai criterion. Ural Math. J., 2023, vol. 9, no. 1, pp. 19–48. http://dx.doi.org/10.15826/umj.2023.1.003
2. Andrews G.E. The theory of partitions. Cambridge, Cambridge Univ. Press, 1984, 255 p. https://doi.org/10.1017/CBO9780511608650
3. Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Ser. Ann. Discr. Math., vol. 56. Amsterdam, North-Holland Publ. Co., 1995, 542 p. https://doi.org/10.1016/S0167-5060(13)71063-X
4. Foldes S., Hammer P.L. Split graphs. In: Proc. of the 8th South-Eastern Conf. on Comb.: Graph Theory and Computing, Baton Rouge, Louisiana State Univ., 1977, pp. 311–315.
5. Hammer P.L., Simeone B. The splittance of a graph. Combinatorica, 1981, vol. 1, pp. 275–284. https://doi.org/10.1007/BF02579333
6. Tyshkevich R.I. Decomposition of graphical sequences and unigraphs. Discrete Math., 2000, vol. 220, no. 1–3, pp. 201–238. https://doi.org/10.1016/S0012-365X(99)00381-7
7. Merris R. Graph theory. NY, J. Wiley and Sons Inc., 2001, 256 p. https://doi.org/10.1002/9781118033043
8. Merris R. Split graphs. Eur. J. Comb., 2003, vol. 24, iss. 4, pp. 413–430. https://doi.org/10.1016/S0195-6698(03)00030-1
9. Baransky V.A., Zuev V.V., Senchonok T.A. Reducing graphs by lifting rotations of edges to splittable graphs. Ural Math. J., 2024, vol. 10, no. 2, pp. 25–36. http://dx.doi.org/10.15826/umj.2024.2.003
10. Fulkerson D.R., Hoffman A.J., McAndrew M.H. Some properties of graphs with multiple edges. Canadian J. Math., 1965, vol. 17, pp. 166–177. https://doi.org/10.4153/CJM-1965-016-2
Cite this article as: V.A. Baransky, T.A. Senchonok. An edge switching procedure and splittable ancestors of a graph.Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 4, pp. 39–51.
