Побудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ні

Анотація

У цій статті розглядаються тільки прості неорієнтовні графи. Проблема пошуку досконалого парування у довiльному простому графi є відомою і популярною в теорії графів. Її застосовують у рiзноманiтних сферах, таких як хiмiя, комбiнаторика, теорiя iгор тощо. Паруванням M у простому графi G називають множину попарно несумiжних ребер, тобто таких, що не мають спiльних вершин.
Парування називають досконалим, якщо воно покриває усi вершини графа, тобто кожна з вершин графа iнцидентна рiвно одному з ребер у досконалому паруваннi. За теоремою Кенiга, регулярнi дводольнi графи додатного степеня завжди мають досконале парування. Проте графи, які не є дводольними, потребують додаткових досліджень.
Мультимножину власних значень матриці суміжності називають спектром графа. Окремою цікавою задачею теорії графів є пошук попарно неізоморфних коспектральних графів, тобто неізоморфних графів з однаковим спектром. У цьому напрямі проводились дослідження щодо пошуку конкретних конструкцій коспетральних пар графів. Крім того, цікавими є знаходження коспектральних графів, які мають додаткові властивості, наприклад, знаходження коспектральних графів, для одного з яких існує досконале парування, а для другого --- ні.

Блазік, Камінгс і Гамерс дослідили, що для кожного існує пара коспектральних зв'язних k-регулярних графів, де один має досконале парування, а інший --- ні. При доведенні цієї теореми автори використали конструкцію перемикання Годзiла--Маккея. За допомогою цієї конструкції у нашій роботі покроково описано побудову пари коспектральних зв’язних 5-регулярних графiв. Для одного з побудованих графів існує досконале парування, яке наведене в цій статті. Для другого побудованого графа досконалого парування не існує. Побудовані графи мають 42 вершини і складаються з 5 блоків, що з’єднані між собою мостами. За допомогою комп’ютерних засобів обчислено спектр побудованих графів. Таким чином перевірено, що пара справді є коспектральною.