УДК 519.176
MSC: 05C35, 05C07
DOI: 10.21538/0134-4889-2025-31-4-39-51
Пусть $r$ — ранг Дёрфи графа $G = (V, E)$, т. е. ранг Дёрфи его степенного разбиения $\mathrm{dpt}(G)$. Пусть $V_1$, $V_2$ — теоретико-множественное разбиение множества вершин $V$ на два непустых подмножества такое, что $\deg v\geq r$ для любого $v$ из $V_1$ и $\deg v \leq r$ для любого $v$ из $V_2$. Двудольный граф $(V_1, E', V_2)$ называется сэндвич подграфом графа $G$, отвечающим паре $V_1$, $V_2$, где $E'$ — множество всех ребер из $E$, которые идут из $V_1$ в $V_2$. Граф называется расщепляемым, если его множество вершин можно представить в виде объединения клики и коклики. Расщепляемый предок графа — это расщепляемый граф, который можно получить из $G$ с помощью некоторого последовательного выполнения повышающих вращений ребер. Расщепляемый предок графа $G$, имеющего ранг Дёрфи $r$, называется ближайшим расщепляемым $r$-предком графа $G$, если его можно получить из $G$ с помощью наименьшего возможного числа $s$ повышающих вращений ребер. Отметим, что $s = \frac{1}{2} (\mathrm{sum}\, \mathrm{tl}(\lambda) - \mathrm{sum}\, \mathrm{hd}(\lambda))$, где $\lambda = \mathrm{dpt}(G)$, $\mathrm{tl}(\lambda)$ — хвост и $\mathrm{hd}(\lambda)$ — голова разбиения $\lambda$. Цель работы состоит в доказательстве следующих двух утверждений. Пусть $r$ — ранг Дёрфи графа $G$, граф $G_1$ получен из графа $G$ с помощью процедуры переключения ребер, отвечающей некоторому чередующемуся $4$-циклу $C$.
1. Если $C$ не является чередующимся $4$-циклом сэндвич подграфа $(V_1, E, V_2)$ графа $G$, то графы $G$ и $G_1$ имеют общего ближайшего расщепляемого $r$-предка.
2. Если $C$ содержится в сэндвич подграфе $(V_1, E', V_2)$ графа $G$, то графы $G$ и $G_1$ имеют общего расщепляемого предка, который получается из каждого из них с помощью последовательности, состоящей не более чем из $s + 1$ повышающих вращений ребер.
Ключевые слова: целочисленное разбиение, графическое разбиение, степенное разбиение, расщепляемый граф, вращение ребра
СПИСОК ЛИТЕРАТУРЫ
1. Baransky V.A., Senchonok T.A. Around the Erdos–Gallai criterion // Ural Math. J. 2023. Vol. 9, no. 1. P. 19–48. https://doi.org/10.15826/umj.2023.1.003
2. Andrews G.E. The theory of partitions. Cambridge: Cambridge Univ. Press, 1976. 255 p. https://doi.org/10.1017/CBO9780511608650
3. Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Ser. Annals Discr. Math. Vol. 56. Amsterdam: North-Holland Publishing Co., 1995. 542 p.
4. Foldes S., Hammer P.L. Split graphs // Proc. of the 8th South-Eastern Conf. on Comb.: Graph Theory and Computing. 1977. P. 311–315.
5. Hammer P.L., Simeone B. The splittance of a graph // Combinatorica. 1981. Vol. 1. P. 275–284. https://doi.org/10.1007/BF02579333
6. Tyshkevich R.I. Decomposition of graphical sequences and unigraphs // Discrete Math. 2000. Vol. 220. P. 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 // European J. Combin. 2003. Vol. 24. P. 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. Vol. 10, № 2. 2024. P. 25–36. https://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. Vol. 17. 1965. P. 166–177. https://doi.org/10.4153/CJM-1965-016-2
Поступила 8.07.2025
После доработки 7.09.2025
Принята к публикации 15.09.2025
Баранский Виталий Анатольевич
д-р физ.-мат. наук, профессор
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: vitaly.baransky@urfu.ru
Сеньчонок Татьяна Александровна
канд. физ.-мат. наук
доцент
Уральский федеральный университет
г. Екатеринбург
e-mail: tatiana.senchonok@urfu.ru
Ссылка на статью: В.А. Баранский, Т.А. Сеньчонок. Операция переключения ребер и расщепляемые предки графа // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 4. С. 39-51
English
V.A. Baransky, T.A. Senchonok. An edge switching procedure and splittable ancestors of a graph
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
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.
