EISSN 2414-3952
Язык: en

Статья: REDUCING GRAPHS BY LIFTING ROTATIONS OF EDGES TO SPLITTABLE GRAPHS (2024)

Читать онлайн

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.

Ключевые фразы: integer partition, graphical partition, degree partition, splittable graph, rotation of an edge
Автор (ы): Баранский Виталий Анатольевич
Соавтор (ы): Зуев В. В., Сеньчонок Татьяна Александровна
Журнал: URAL MATHEMATICAL JOURNAL

Предпросмотр статьи

Идентификаторы и классификаторы

УДК
51. Математика
Для цитирования:
БАРАНСКИЙ В. А., ЗУЕВ В. В., СЕНЬЧОНОК Т. А. REDUCING GRAPHS BY LIFTING ROTATIONS OF EDGES TO SPLITTABLE GRAPHS // URAL MATHEMATICAL JOURNAL. 2024. Т. 10 № 2 (19)
Текстовый фрагмент статьи