RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2021, том 504, страницы 21–46 (Mi znsl7108)

Преобразования сборного числа 4-регулярного графа

А. Э. Гутерманabc, Е. М. Крейнесcb, Н. В. Остроуховаb

a Московский физико-технический институт, Долгопрудный, 141701, Россия
b Московский гос. университет им. М. В. Ломоносова, Москва, 119991, Россия
c Московский центр фундаментальной и прикладной математики, Москва, 119991, Россия

Аннотация: Простые сборные графы характеризуют процесс рекомбинации ДНК у простейших. Важными характеристиками этих графов являются сборное число, количество различных гамильтоновых множеств полигональных путей, односторонняя и двусторонняя аддитивность графа. В работе исследуются преобразования простых сборных графов, позволяющие увеличивать сборное число или получать двусторонне аддитивные графы. Определено минимальное число петель, которые необходимо добавить на ребра петельного графа, чтобы увеличить его сборное число на 1. Библ. – 7 назв.

Ключевые слова: сборные графы, 2-слова, сборное число.

УДК: 512.543+519.177

Поступило: 13.10.2021



© МИАН, 2024