Том 4

Permanent URI for this collection

https://ekmair.ukma.edu.ua/handle/123456789/23004

Browse

Browsing Том 4 by Subject "Godsil-McKay switching"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Побудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ні
    (2021) Соболєв, Владислав; Соломко, Вікторія
    У цій статті розглядаються тільки прості неоріентовні графи. Проблема пошуку досконалого парування у довільному простому графі є відомою і популярною в теорії графів. Її застосовують у різноманітних сферах, таких як хімія, комбінаторика, теорія ігор тощо. Паруванням М у простому графі О називають множину попарно несуміжних ребер, тобто таких, що не мають спільних вершин. Парування називають досконалим, якщо воно покриває усі вершини графа, тобто кожна з вершин графа інцидентна рівно одному з ребер у досконалому паруванні. За теоремою Кеніга, регулярні дводольні графи додатного степеня завжди мають досконале парування. Проте графи, які не є дводольними, потребують додаткових досліджень. Мультимножину власних значень матриці суміжності називають спектром графа. Окремою цікавою задачею теорії графів є пошук попарно неізоморфних коспектральних графів, тобто неізоморфних графів з однаковим спектром. У цьому напрямі проводились дослідження щодо пошуку конкретних конструкцій коспетральних пар графів. Крім того, цікавими є знаходження коспектральних графів, які мають додаткові властивості, наприклад, знаходження коспектральних графів, для одного з яких існує досконале парування, а для другого — ні. Блазік, Камінгс і Гамерс дослідили, що для кожного к > 5 існує пара коспектральних зв’язних к-регулярних графів, де один має досконале парування, а інший — ні. При доведенні цієї теореми автори використали конструкцію перемикання Годзіла Маккея. За допомогою цієї конструкції у нашій роботі покроково описано побудову пари коспектральних зв’язних 5-регулярних графів. Для одного з побудованих графів існує досконале парування, яке наведене в цій статті. Для другого побудованого графа досконалого парування не існує. Побудовані графи мають 42 вершини і складаються з 5 блоків, що з’єднані між собою мостами. За допомогою комп’ютерних засобів обчислено спектр побудованих графів. Таким чином перевірено, що пара справді є коспектральною.